-
Notifications
You must be signed in to change notification settings - Fork 1
Bit Manipulation
Working on bytes, or data types comprising of bytes like ints, floats, doubles or even data structures which store a large number of bytes is normal for a programmer. In some cases, a programmer needs to go beyond this - that is to say that in a deeper level where the importance of bits is realized.
Operations with bits are used in Data compression (data is compressed by converting it from one representation to another, to reduce the space), Exclusive-Or Encryption (an algorithm to encrypt the data for safety issues). In order to encode, decode or compress files we have to extract the data at the bit level. Bitwise Operations are faster and closer to the system and sometimes optimize the program to a good level.
We all know that 1 byte comprises of 8 bits and an integer or character can be represented using bits in computers, which we call its binary form (contains only 1 or 0) or in its base 2 form.
Example:
-
14 = {1110}
= 1 * 23 + 1 * 22 + 1 * 21 + 0 * 20
= 14. -
20 = {10100}
= 1 * 24 + 0 * 23 + 1 * 22 + 0 * 21 + 0 * 20
= 20.
For characters, we use ASCII representation, which is in the form of integers which again can be represented using bits as explained above.
Signed numbers can represent both positive and negative numbers. The datatype int is signed. For n bit binary number, 1 bit is reserved for sign symbol. If the value of sign bit is 0, then the given number will be positive, else if the value of sign bit is 1, then the given number will be negative. The rest of the n-1 digits represent magnitude of the number. The sign bit is the most significant bit, and has value -2n-1.
Example:
-7 = {1001}
= 1 * (-23) + 0 * 22 + 0 * 21 + 1 * 20
= -7
Unsigned numbers represent positive values only. The representation is just like normal binary representation.
There are different bitwise operations used in bit manipulation. These bitwise operations operate on the individual bits of the bit patterns. Bit operations are fast and can be used in optimizing time complexity. Some common bitwise operators are:
NOT ( ~ ): Bitwise NOT is a unary operator that flips the bits of the number i.e., if the ith bit is 0, it will change it to 1 and vice versa. Bitwise NOT is nothing but simply the one’s complement of a number. Let's take an example.
N = 5 = (0101)2
~N = ~5 = ~(0101)2 = (1010)2 = -6 (signed representation)
N = 5 = (0000000000000101)2
~N = (1111111111111010)2 = 65530 (unsigned, 16 bit representation)
AND ( & ): Bitwise AND is a binary operator that operates on two equal-length bit patterns. If both bits in the compared position of the bit patterns are 1, the bit in the resulting bit pattern is 1, otherwise 0.
A = 5 = (101)2 , B = 3 = (011)2
A & B = (101)2 & (011)2 = (001)2 = 1
OR ( | ): Bitwise OR is also a binary operator that operates on two equal-length bit patterns, similar to bitwise AND. If both bits in the compared position of the bit patterns are 0, the bit in the resulting bit pattern is 0, otherwise 1.
A = 5 = (101)2 , B = 3 = (011)2
A | B = (101)2 | (011)2 = (111)2 = 7
XOR ( ^ ): Bitwise XOR also takes two equal-length bit patterns. If both bits in the compared position of the bit patterns are 0 or 1, the bit in the resulting bit pattern is 0, otherwise 1.
A = 5 = (101)2, B = 3 = (011)2
A ^ B = (101)2 ^ (011)2 = (110)2 = 6
Left Shift ( << ): Left shift operator is a binary operator which shifts some number of bits, in the given bit pattern, to the left and appends 0 at the end. Left shift is equivalent to multiplying the bit pattern by 2k ( if we are shifting k bits ).
Right Shift (>>) : Right shift operator is a binary operator which shifts some number of bits, in the given bit pattern, to the right and appends 1 at the end for signed numbers and append 0 at the end for unsigned numbers. Right shift is equivalent to dividing the bit pattern by 2k ( if we are shifting k bits ).
Consider a number N and you need to find if N is a power of 2. A simple solution to this problem is to repeated divide N by 2 if N is even. If we end up with a 1 then N is a power of 2, otherwise not. There is a special case also. If N = 0 then it is not a power of 2. The time complexity of this method is O(log2 N). But there's a better way of doing this, using bit manipulation.
Think of the binary representation of a number that is a power of 2. And now compare it with the binary representation of that number - 1.
Example:
23 = 8 = (1000)2.
7 = (0111)2
Consider a number x that we need to check for being a power for 2. Now think about the binary representation of (x-1).(x-1) will have all the bits same as x, except for the rightmost 1 in x and all the bits to the right of the rightmost 1.
Binary representation of (x-1) can be obtained by simply flipping all the bits to the right of rightmost 1 in x and also including the rightmost 1 position.
So it can be observed that x&(x-1), for x that is a power of 2, will always be 0. We are sure that it won't be 0 for x that is not a power of 2. Hence we can come up with the following code:
bool isPowerOfTwo(int x)
{
// x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
return (x && !(x & (x - 1)));
}In the above code && is logical AND, ! is logical NOT.
The basic approach to evaluate the binary form of a number is to traverse on it and count the number of ones. But this approach takes log2N of time in every case.
Why log2N ? As to get a number in its binary form, we have to divide it by 2, until it gets 0, which will take log2N of time.
With bitwise operations, we can use an algorithm whose running time depends on the number of ones present in the binary form of the given number. This algorithm is much better, as it will reach to log N, only in its worst case.
int count_one (int n)
{
while( n )
{
n = n&(n-1);
count++;
}
return count;
}Why this algorithm works ? As explained in the previous algorithm, the relationship between the bits of x and x-1. So as in x-1, the rightmost 1 and bits right to it are flipped, then by performing x&(x-1), and storing it in x, will reduce x to a number containing number of ones(in its binary form) less than the previous state of x, thus increasing the value of count in each iteration.
Example: n = 23 = {10111}2 .
- Initially, count = 0.
- Now, n will change to n&(n-1). As n-1 = 22 = {10110}2 , then n&(n-1) will be {10111}2 & {10110}2, which will be {10110}2 which is equal to 22. Therefore n will change to 22 and count to 1.
- As n-1 = 21 = {10101}2 , then n&(n-1) will be {10110}2 & {10101}2, which will be {10100}2 which is equal to 20. Therefore n will change to 20 and count to 2.
- As n-1 = 19 = {10011}2 , then n&(n-1) will be {10100}2 & {10011}2, which will be {10000}2 which is equal to 16. Therefore n will change to 16 and count to 3.
- As n-1 = 15 = {01111}2 , then n&(n-1) will be {10000}2 & {01111}2, which will be {00000}2 which is equal to 0. Therefore n will change to 0 and count to 4.
- As n = 0, the loop will terminate and give the result as 4.
Time Complexity: O(K), where K is the number of ones present in the binary form of the given number.
To check if the ith bit is set or not (1 or not), we can use AND operator. How?
Let’s say we have a number N, and to check whether it’s ith bit is set or not, we can AND it with the number 2i. The binary form of 2i contains only ith bit as set (or 1), else every bit is 0 there. When we will AND it with N, and if the ith bit of N is set, then it will return a non zero number ( 2i to be specific), else 0 will be returned.
Using Left shift operator, we can write 2i as 1 << i . Therefore:
bool check (int N)
{
if( N & (1 << (i - 1) )
return true;
else
return false;
}Example: Let’s say N = 20 = {10100}2.
Now let’s check if it’s 2nd bit is set or not(starting from 0).
For that, we have to AND it with 22 = 1 << 2 = {100}2.
{10100}2 & {100}2 = {100}2 = 4(non-zero number), which means it’s 2nd bit is set.
For a given bit position in 2 operands, XOR gives 1 if the 2 bits are different, and 0 if they're the same. Hence x^x = 0, and 0^x = x.