Bit Manipulation Flashcards Preview

Algorithms & Data Structures > Bit Manipulation > Flashcards

Flashcards in Bit Manipulation Deck (14)
Loading flashcards...
1
Q

One’s Compliment

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

Two’s Compliment

A
  • 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)
3
Q

Bitwise Operations

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

Bitwise And

A
  • &
  • Only 1 if all bits are 1
5
Q

Bitwise Or

A
  • |
  • Returns 1 if any bit is 1
6
Q

Bitwise XOR

A
  • 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 (!=)
7
Q

Not

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

Left Shift

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

Right Shift

A
  • >> 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
10
Q

Set ith Bit

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

Steps

  • Create set mask
    • Left Shift (<<) 1 to ith position
  • Bitwise Or ( | ) mask and number
11
Q

Clear ith Bit

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

Steps

  1. Create clearing mask
    1. Left Shift (<<) 1 to ith position
  2. Not (~) the mask
  3. Bitwise And (&) mask and number
12
Q

Flip ith Bit

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

Steps

  • Create flip mask
    • Left Shift (<<) 1 to ith position
  • Bitwise XOR ( ^ ) mask and number
13
Q

Check ith Bit

A
  • 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
14
Q

Logical vs Arithmetic Shift

A
  • 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