Overview: Bit Manipulation

Bit manipulation is used in different varieties of problem. Bit is one of the most effective and efficient low-level optimization technique.

Bit Operators:

The bit-manipulation approach lies around the use of bit-wise operators & (and), | (or), ~ (not) and ^ (xor).  The first three of them we are already familiar through their boolean form (&&, ||, !).  Have a quick re-cap of the following table :

The bit-wise versions of the operations are the same, except that instead of interpreting their arguments as true or false, they operate on each bit of the arguments. Thus, if A is 1010 and B is 1100,

• A & B = 1000
• A | B = 1110
• A ^ B = 0110
• ~A = 11110101 (the number of 1’s depends on the type of A).

Remember that   :

‘&‘  indicates  ‘AND‘ operation,

‘|‘ indicates  ‘OR‘ operation,

‘~‘ indicates ‘NOT‘ operation,

‘^‘ indicates ‘XOR‘ operation

The other two operators we will discuss are :  “<<” and “>>“. The former is Left Shift operator and the later is Right Shift operator.

=>  a << b  : This shifts all the bits in a to the left by b positions.

=>  a   >>  b  : This shifts all the bits in a to the right by b positions.

For simplicity you can think left shifting by b as multiplication with  2^b and right shifting by b as division with 2^b.

i.e.   a << b  = a * 2^b

         a >> b = a / 2^b

The most common use for shifting is to access a particular bit, for example, 1 << x is a binary number with bit x set and the others clear (bits are almost always counted from the right-most/least-significant bit, which is numbered 0).

In general, we will use an integer to represent a set on a domain of up to 32 values (or 64, using a 64-bit integer), with a 1 bit representing a member that is present and a 0 bit one that is absent. Then the following operations are quite straightforward, where ALL_BITS is a number with 1’s for all bits corresponding to the elements of the domain:

If in bit-s representation the number has i-th bit as 0 it is called unset bit and if i-th bit is 1 it is called set bit.

Some interesting bit-magics:

 

1) If you XOR a bit with its own negated value, you will always get 1. Therefore the solution to a ^ (~a)  will be the sequence of 1s.

consider a is of data-type byte.

example:

a = 00000001

~a  = 11111110

Now a ^ (~a) = 11111111

 

2) An operation like x & (~0 << n) clears the n rightmost bits of x. The value ~o is the sequences of 1s, so by shifting it by n, we have a bunch of ones followed by n zeros. By doing AND we clear the the rightmost n digits of x.

 

3) Bit Facts and Tricks:

x ^ 0’s = x                                       x & 0’s = 0                          x | 0’s = x

x ^ 1’s = ~x                                     x & 1’s = x                            x | 1’s = 1’s

x ^ x = 0                                         x & x = x                               x | x = x

 

4)  Get Bit :

If I want to get the bit at i-th position, this method shifts 1 over by i bits , creating a value and performing an AND operation with the number num. If the resultant value is zero, that bit is unset else, that bit is set.

boolean getBit(int num, int i) {
    return ((num & (1 << i)) != 0);
}

 

5) Set Bit:

If I want to set the bit at i-th position, this method shifts 1 over by i bits , creating a value and performing an OR operation with the number num.

public int setBit(int num, int i) {
    return num | (1 << i);
}

 

6) Clear Bit:

This method operates in reverse way as the setBit method works. To clear the i-th bit we first negate the result obtained from 1 << i and perform AND operation with the number num.

public int clearBit(int num, int i) {
    int mask = ~(1 << i);
    return num & mask;
}

7) Clear all the MSB through i (inclusive)

This method is meant for clearing all the MSB’s (Most Significant Bits) through i (inclusive) we do:

public int clearBitsMSBThrough(int num, int i) {
    int mask = ( 1 << (i + 1) ) - 1;
    return num & mask;
}

8) Clear all the bits from i through o(inclusive)

This method is meant for clearing all the bits from i through 0 from the number num:

public int clearBitsIthrough0(int num, int i) {
    int mask = ~(1 << (i + 1)) - 1;
    return num & mask;
}

Bit magic : Check if a number is power of 2

Problem Statement:  How do you check if a number of power of 2 or not. i.e. if the number is one among 1, 2, 4, 8, 16, … and so on.

Approach:  A number is power of two means it has only one set bit. Let’s say that number can be stored with ‘x’ bits. A number just less than n i.e. (n – 1) will have (x – 1) set bits and the x-th bit being unset.

For example :

n = 16 ;    1 0 0 0 0

Therefore, n – 1 = 15 ;    0 1 1 1 1

i.e. n & (n – 1)  is equals to zero(0).

Thus, the above property depicts that if n & (n – 1) == 0 , then ‘n‘ is the power of 2.

public boolean isPowerOfTwo(int n)
{
    return (n & (n - 1)) == 0;
}

Bit Practice Questions

The following two questions will clear your bits-concept to some extent.

http://community.topcoder.com/stat?c=problem_statement&pm=11791&rd=14727&rm=311688&cr=22859464

http://community.topcoder.com/stat?c=problem_statement&pm=10878&rd=14156

Due to copy-right issues, I cannot directly have the same questions here. You feel free to refer these questions through Topcoder’s site.