# 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))