Bit Manipulation
Bit manipulation is a basic concept in computer science and it would be a fair question for a technical interview. You should be comfortable by doing operations on binary numbers. Moreover, there are some basic bit manipulations that most of the other bit manipulations derive from these ones. Needless to say it would be useful to practice such problems.
Let’s start with the representation of binary numbers in Python. By running the command \(bin(13)\) we get the string \(“0b1101″\) which is the binary representation of \(13\). For the reverse command, we can run \(int( “0b1101”, 2)\) which will output the number \(13\). This is the relationship between decimal numbers and their equivalent in binary strings. Now, let’s refresh some basic binary operations such as: sum (+), subtraction (-), multiplication (*), shift (>>), xor (^), and (&), or (|), and not (~). From the following table try to calculate the resulting output of each of the above operations:
0b100 + 0b110 | 0b0110 + 0b10 | 0b0110 * 0b11 | 0b1010 + 0b1010 |
0b1100 – 0b110 | 0b110 & 0b0101 | 0b110 ^ 0b0101 | 0b110 | 0b0101 |
3<<2 | 0b10101 >> 2 | ~0b1010 | 0b1011 & ~0b1011 |
- The right shift operation shifts the digits of a number in binary by a specified
location on the right. For example, the command \(4 >> 1 \) will result to \(2\) (\((4)_2=100\)
and \((2)_2=10\)). - The left shift operation shifts the digits of a number in binary by a specified
location on the left. For example, the command \(4 << 1 \) will result to \(8\) (\((4)_2=100\)
and \((8)_2=1000\)). - Performs the logical AND in the binary representations of the numbers.
For example, \(8 \, \& \, 5\) will result to \(0\). - Performs the logical OR in the binary reoresentations of the numbers. For,
example \(4 \, | \, 2\) will result to \(6\). - Performs the logical XOR in the binary representations of the numbers. – For example, \(7 \, \hat{} \, 2\) will result to \(5\) (\((2)_2=10\), \((7)_2=111\), and \((5)_2=101\)).
- In Python the bitwise not is confusing. As an operator on a number should just flip the bits (from 0 to 1 and vice versa). However, in Python \(\texttildelow\) a returns \(-a-1\).
- You can write numbers in binary format by starting the number with 0b. When doing so, the numbers can be operated on like any other number. For example the code \(\textbf{print(0b101)} will print \)latex 4$. The command \\(textbf{bin(number)}\) takes the integer number as input and returns the binary representation of that integer in a string. Similarly, we can use the functions oct() for 8-base and hex() for 16-base.
- The command \(\textbf{int(a,baseA)}\) takes the string a and returns the number a which is written in the base baseA, the result is in decimal system.