Bit Manipulation

Bit manipulation is used in a variety of problems. Sometimes, the question explicitly calls for bit manipulation. Other times, it's simply a useful technique to optimize your code.

Bit Facts and Tricks

OR

x | 0s = x
x | 1s = 1
x | x = x

AND

x & 0s = 0
x & 1s = x
x & x = x

XOR

x ^ 0s = x
x ^ 1s = ~x
x ^ x = 0

Two's Complement and Negative Numbers

Computer typically store integers in two's complement representation. A positive number is represented as itself while a negative number is represented as the two's complement of its absolute value (with a 1 in its sign bit to indicate that a negative number).

The two's complement of an N-bit number (where N is the number of bits used for the number, excluding the sign bit) is the complement of the number with respect to 2^N.

Lets suppose a 4-bit number and represent -3. The complement of -3 with respect to 2^3 is 5. In binary 5 is 101. Therefore, -3 as a 4-bit number is 1101 with the first bit being the sign bit.

In other words, the binary representation of -K as an N-bit number is concat(1, 2^(N-1) - K).

Another way to look at this is that we invert the bits in the positive representation and then add 1. In binary 3 is 011. Flip the bits to get 100, add 1 to get 101, then prepend the sign bit 1 to get 1101.

Logical and Arithmetic Shift

A single Bit is the basic unit of Storage, stores either 1 or 0. Therefore as bits move left or right in a value of specific type, their values change. Moving bits in a value in C Language is performed using Left or Right Shift Operators. These operators work on individual bits of values of variables of Integer Data Type in their signed or unsigned form. Characters are internally integers and these operators, therefore, work with them.

Left shift operator is represented by << and right shift by >>. These operators are Binary operators, require two operands on either side and both must be integers.

Logical Shift

Shifting is called to be Logical when performed on unsigned integers in either direction. In Logical Shift, during shifting either side, empty slots are padded with Zeros.

int main(void)
{
    unsigned int x = 8;
    unsigned int y = 8;

    x >>= 1;    // Right Shift by 1
    y <<= 1;    // Left  Shift by 1

    printf("After Right Shift, x = %d \n", x);
    printf("After Left  Shift, y = %d \n", y);
}

Output:

After Right Shift, x = 4 
After Left  Shift, y = 16

• Shifting a value to the right by n bits has the effect of dividing the value by the power of 2 raised to n.
• shifting the value to left by n bits has the effect of multiplying value by power of 2 raised to n.

Arithmetic Shift

Arithmetic and Logical left shifts are Identical. Only the right shifts differ, and then only for negative values. Therefore, programs that do right shifts on signed values are inherently non-portable.

Arithmetic Right Shift

In an arithmetic right shift, we shift values to the right but fill in the new bits with the value of the sig bit.

With continuous right shifting an unsigned number, we would get 0 because we are shifting a zero in the most significant bit repeatedly.
For a signed negative number, we would get -1 because we are shifting a one into the most significant bit.

Common Bit Tasks

Set Bit

Function:

int SetBit(int Num, int BitIndex)
{
    return num | (1 << BitIndex);
}

Macro:

#define     SET_BIT(Num, BitIndex)      (Num |= (1 << BitIndex))

Clear Bit

Function:

int ClearBit(int Num, int BitIndex)
{
    int mask = ~(1 << BitIndex);

    return Num & mask;
}

Macro:

#define     CLR_BIT(Num, BitIndex)      (Num &= (~(1 << BitIndex)))

To Clear all bits from the MSB through BitIndex (inclusive):

int ClearBitsMSBthroughBitIndex(int Num, int BitIndex)
{
    int mask = (1 << BitIndex) - 1;

    return Num & mask;
}

To clear all bits from BitIndex through the LSB (inclusive):

int ClearBitsBitIndexthroughLSB(int Num, int BitIndex)
{
    int mask = (-1 << (BitIndex + 1));

    return Num & mask;
}

Get Bit

Function:

int GetBit(int Num, int BitIndex)
{
    return Num & (1 << BitIndex);
}

Macro:

#define     GET_BIT(Num, BitIndex)      (Num &= (1 << BitIndex))

Toggle Bit

Function:

int ToggleBit(int Num, int BitIndex)
{
    return Num ^ (1 << BitIndex);
}

Macro:

#define     TGL_BIT(Num, BitIndex)      (Num ^= (1 << BitIndex))

Update Bit

To set the ith bit to a value, we first clear the bit at that position, then we shift the intended value.

Function:

int UpdateBit(int Num, int BitIndex, int Value)
{
    int mask = ~(1 << BitIndex);

    Num &= mask;

    Num |= (Value << BitIndex);
}

Macro:

#define     UPDATE_BIT(Num, BitIndex, Value)    ((Num = (Num & (~(1 << BitIndex)) | (Value << BitIndex))))

Problem Solving

Problem Solving on Bit Manipulation through this link.