Skip to main content

Bit Manipulation

Bitwise Operators​

  • &: AND
  • |: OR
  • ^: XOR
  • ~: NOT
  • <<: Binary Left Shift
  • >>: Binary Right Shift
  • >>>: Zero Fill Right Shift

Bit Facts & Tricks​

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

Two's Complement​

  • Computers typically store integers in two's complement representation.
  • Range of unsigned numbers that can be stored with N bits is 0 - +(2^N - 1).
  • Range of signed numbers that can be stored with N bits in two's complement representation is -(2^(N - 1)) - +(2^(N - 1) - 1).
  • Binary representation of -K is concat(1, bin(2^(N - 1) - K)). Another way to compute it is to flip the bits of the binary representation of K, add 1 and then prepend the sign bit 1.

Arithmetic vs. Logical Shift​

  • In an arithmetic right shift (>>), the bits are shifted and the sign bit is put in the MSB.
  • In a logical right shift (>>>), the bits are shifted and a 0 is put in the MSB.

Common Bit Tasks​

Get Bit​

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

Set Bit​

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

Clear Bit(s)​

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

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

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

Toggle Bit​

int toggleBit(int num, int i) {
    return num ^ (1 << i);
}

Update Bit​

int updateBit(int num, int i, boolean setBit) {
    int value = setBit ? 1 : 0;
    int mask = ~(1 << i);
    return (num & mask) | (value << i);
}

Multiply/Divide by 2n​

num = num << n;   // multiply
num = num >> n;   // divide