DEV Community

Ahmed Gouda
Ahmed Gouda

Posted on • Updated on • Originally published at ahmedgouda.hashnode.dev

 

Bit Manipulation

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
Enter fullscreen mode Exit fullscreen mode

AND

x & 0s = 0
x & 1s = x
x & x = x
Enter fullscreen mode Exit fullscreen mode

XOR

x ^ 0s = x
x ^ 1s = ~x
x ^ x = 0
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

Output:

After Right Shift, x = 4 
After Left  Shift, y = 16 
Enter fullscreen mode Exit fullscreen mode
  • 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);
}
Enter fullscreen mode Exit fullscreen mode

Macro:

#define     SET_BIT(Num, BitIndex)      (Num |= (1 << BitIndex))
Enter fullscreen mode Exit fullscreen mode

Clear Bit

Function:

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

    return Num & mask;
} 
Enter fullscreen mode Exit fullscreen mode

Macro:

#define     CLR_BIT(Num, BitIndex)      (Num &= (~(1 << BitIndex)))
Enter fullscreen mode Exit fullscreen mode

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

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

    return Num & mask;
}
Enter fullscreen mode Exit fullscreen mode

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

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

    return Num & mask;
}
Enter fullscreen mode Exit fullscreen mode

Get Bit

Function:

int GetBit(int Num, int BitIndex)
{
    return Num & (1 << BitIndex);
}
Enter fullscreen mode Exit fullscreen mode

Macro:

#define     GET_BIT(Num, BitIndex)      (Num &= (1 << BitIndex))
Enter fullscreen mode Exit fullscreen mode

Toggle Bit

Function:

int ToggleBit(int Num, int BitIndex)
{
    return Num ^ (1 << BitIndex);
}
Enter fullscreen mode Exit fullscreen mode

Macro:

#define     TGL_BIT(Num, BitIndex)      (Num ^= (1 << BitIndex))
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

Macro:

#define     UPDATE_BIT(Num, BitIndex, Value)    ((Num = (Num & (~(1 << BitIndex)) | (Value << BitIndex))))
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Advice For Junior Developers

Advice from a career of 15+ years for new and beginner developers just getting started on their journey.