Bit Manipulation

OR

  • OR is used for setting a bit regardless of the other bit.
  • When you want to set a bit to 1, just ‘OR’ the bit with 1
  • If x denotes a bit(0 or 1), then the following hold true.
  • x | 0 = x (i.e. OR ing with 0 retains the original bit.)
  • x | 1 = 1 (i.e. OR ing with 1 sets the bit to 1.)

Examples

  • Set the last digit to 1
    x | 1
  • Set the number to its closest even number (i.e. set the last digit to 0)
    (x | 1) - 1
  • Set the k-th digit to 1, e.g. 0b101001 -> 0b101101, k=3
    x | (1 << (k-1))
  • Set the last k digits to 1, e.g. 0b101001 -> 0b101111, k=3
    x | (1 << k - 1)
  • Flip the last continuous 0’s to 1’s, e.g. 0b10110000 -> 0b10111111
    x | (x-1)
  • Flip the first 0 to 1 (starting from right), e.g. 0b10101011 -> 0b10101111
    x | (x+1)

 

AND

  • AND can be used for clearing a bit.
  • When you want to ‘clear’ a bit, just ‘AND’ it with 0.
  • AND can be used for checking whether a bit is set.
  • To check whether a bit is set, just ‘AND’ it with 1, it will return whether that bit was set.
  • If x denotes a bit(0 or 1), then the following hold true.
  • x & 0 = 0 (i.e. AND ing with 0 clears the bit to 0)
  • x & 1 = x (i.e. AND ing with 1 retains the original bit)

Examples

  • What’s the k-th digit of x?
    (x >> (k-1)) & 1
  • Is a number odd? (I.e., Is the last digit 1?)
    (x & 1) == 1
  • What’s the last k digits of x?
    x & (1 << k - 1)
  • What’s the last 3 digits of x?
    x & 0x111
  • Set the k-th digit to 0, e.g. 0x101101 -> 0x101001, k=3
    x & ~(1 << (k-1))
  • Is a number pow of 2?
    (x != 0) && (x & (x-1) ==0), i.e. x && !(x & (x - 1))
  • Flip the last continuous 1’s to 0’s, e.g. 0b10101111 -> 0b10100000
    x & (x+1)
  • N & 0xFF = least significant byte of integer or the last 8 bits of integer.

 

XOR

  • for flipping selective bits, XOR is chosen.
  • for flipping a bit, XOR it with 1, it will get reversed.
  • If x denotes a bit(0 or 1), then the following hold true.
  • x ^ 1 = ~x (XOR ing with 1 flips the bits)

Examples

  • Flip k-th digit
    x ^ (1 << (k-1))
  • Flip last k digits
    x ^ (1 << k - 1)
  • Get the last continuous 1’s, e.g. 0b10101111 -> 0b1111
    (x ^ (x+1)) >> 1
  • Remove the left of the first 1 from the right, e.g. 0b10101000 -> 0b1000
    (x ^ (x-1)) >> 1 + 1   or   x ^ (x-1) & x
  • Swap two numbers
    One way to swap two numbers is to use + and – (two inverse operations):
    a = a + b;  b = a - b;  a = a - b;
    And we can use xor and since its inverse operation is itself:
    a = a ^ b;  b = a ^ b;  a = a ^ b;

 

NOT

  • The bitwise complement operator, ~, flips every bit in a number.

Examples

  •  ~N + 1 = -N

 

SHIFT

  • Left Shift
    • symbol is ‘<<‘
    • x << y means x shifted y bits to the left.
    • If you run out of space, bits drop off from the left.
  • Right Shift
    • symbol is ‘>>’
    • x >> y means x shifted y bits to the right.
    • If you run out of space, bits drop off from the right.

Examples

  • Remove the last digit
    x >> 1
  • Add a 0 to the end of a number
    x << 1
  • Add an 1 to the end of a number
    x << 1 + 1
  • N << 1 = N*2
  • N << 2 = N*pow(2,2)
  • N << k = N*(pow(2,k))
  • N >> 1 = floor(N/2)
  • N >> 2 = floor(N/pow(2,2))
  • N >> k = floor(N/pow(2,k))