http://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

Advertisements

Skip to content
# Category: Summary

# Tree Traversal

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