Bit Manipulation

Question 1

One’s Compliment

Answer 1

• Value obtained by inverting all the digits in a binary number
• Cannot be used to represent negative numbers, because you would have two zeroes

Question 2

Two’s Compliment

Answer 2

• Used to get negative representation of numbers

Steps

1. Write number in binary
2. Invert digits (one’s compliment)
3. Add 1
4. Discard any extra 1’s (in front)

Question 3

Bitwise Operations

Answer 3

• & - And
• | - Or
• ^ - Xor
• ~ - Not
• << - Left shift
• >> - Right Shift

Question 4

Bitwise And

Answer 4

• &
• Only 1 if all bits are 1

Question 5

Bitwise Or

Answer 5

• |
• Returns 1 if any bit is 1

Question 6

Bitwise XOR

Answer 6

• Also known as exclusive-or
• Returns true if only 1 input is true (but not both)
• For more than 2 inputs, returns true if number of 1’s is odd
• Logically equivalent to not equals (!=)

Question 7

Not

Answer 7

• ~
• Flips all bits
• Basically performs one’s compliment on a binary number

Question 8

Left Shift

Answer 8

• << x
• Shifts bits to left by x locations
• Add x 0’s to the right
• Has the effect of multiplying number by 2^x
• Often used to construct bit masks

Question 9

Right Shift

Answer 9

• >> x
• Shifts bits to left by x locations
• Add’s leading 0’s to the front
  
  • Will preserve sign if doing arithmetic shifting
• Has the effect of halfing number (and flooring it) with each shift

Question 10

Set i^th Bit

Answer 10

• Activate (set) any bit by ‘or-ing’ it with 1

Steps

• Create set mask
  
  • Left Shift (<<) 1 to i^th position
• Bitwise Or ( | ) mask and number

Question 11

Clear i^th Bit

Answer 11

• Clear any bit by ‘and-ing’ it with 0

Steps

1. Create clearing mask
   
   1. Left Shift (<<) 1 to i^th position
2. Not (~) the mask
3. Bitwise And (&) mask and number

Question 12

Flip i^th Bit

Answer 12

• Flip a bit by ‘xor-ing’ it with 1
• xor-dinary flipper

Steps

• Create flip mask
  
  • Left Shift (<<) 1 to i^th position
• Bitwise XOR ( ^ ) mask and number

Question 13

Check i^th Bit

Answer 13

• Check a bit by ‘and-ing’ it with 1 and checking the result

Steps

1. Create check mask
   
   1. Left Shift (<<) 1 to position you want to set
2. Bitwise AND ( & ) mask and number
3. Evaluate result
   
   1. If true (not 0), bit was 1
   2. If false (0), but was 0

Question 14

Logical vs Arithmetic Shift

Answer 14

• Applies to right shifts
• Logical right shifts don’t consider the sign bit
  
  • Adds a leading 0 to the left
• Arithmetic right shifts preserve the sign bit
  
  • Adds a leading 1 or a 0 to the left, depending on original number’s sign