Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Cracking the Coding Interview > Ch 5: Bit Manipulation > Flashcards

Ch 5: Bit Manipulation Flashcards

1
Q

Bit Manipulation:
Important Concepts

A
  • Basic Bitwise Operations
  • Bit Tricks
  • Two’s Complement
  • Shifts: Arithmetic vs Logical
  • Common Bit Tasks
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Bit Operators:
Three Types of Operators

A
  • Basic Arithmetic
  • Boolean Operators
  • Shifts
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Bit Operators:
Basic Arithmetic Operators

A
  • Addition: +
  • Subtraction: -
  • Multiplication: *
  • Division: \
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Bit Operators:
Boolean Operators

A
  • Bitwise AND: &
  • Bitwise OR: |
  • Bitwise Exclusive OR(XOR): ^
  • Bitwise NOT: ~ * Bitwise
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Bit Operators:
Shifts

A

Arithmetic Shifts:
* Left: «
* Right:&raquo_space;

Logical Shifts:
* Left: «<
* Right:&raquo_space;>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Bitwise Identities:
X | 0s = ?

A

X | 0s = X

For each bit in X
If 1, operation is 1 | 0 = 1
If 0, operation is 0 | 0 = 0

So, no bits in the result are different from X

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Bit Identities:
X ^ 1s = ?

A

X XOR all ones

X ^ 1s = ~X

For a bit in X:
If 1, 1 ^ 1 = 0
If 0, 0 ^ 1 = 1

All bits are flipped to the opposite

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Bit Identities:
X ^ 0s = ?

A

X XOR all zeros

X ^ 0s = X

For a bit in X:
If 1, 1 ^ 0 = 1
If 0, 0 ^ 0 = 0

All bits in the result are the same as X

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Bit Identities:
X ^ X = ?

A

X XOR X

X ^ X = 0

For each bit in X:
If 1, 1 ^ 1 = 0
If 0, 0 ^ 0 = 0

All bits are set to 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Bit Identities:
X & 0 = ?

A

X AND 0

X & 0 = 0

For a bit in X:
If 1, 1 & 0 = 0
If 0, 0 & 0 = 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Bit Identities:
X & 1s

A

X AND all ones

X & 1s = X

For a bit in X:
If 1, 1 & 1 = 1
If 0, 1 & 0 = 0

No bits are changed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Bit Identities:
X & X

A

X AND X

X & X = X

For a bit in X:
If 1, 1 & 1 = 1
If 0, 0 & 0 = 0

No bits are changed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Bit Identities:
X | 1s

A

X OR all ones

X | 1s = 1s

For a bit in X:
If 1, 1 | 1 = 1
If 0, 0 | 1 = 1

All bits become ones

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Bit Identities:
X | X = ?

A

X OR X

X | X = X

For a bit in X:
If 1, 1 | 1 = 1
If 0, 0 | 0 = 0

No bits are changed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Bit Tricks:
Add a number to itself:

X + X

A
  • Adding a number to itself is equivalent to multiplying it by 2
  • Multiplying by 2 is equivalent to an Arithmetic Left Shift of 1
    2X = X &laquo_space;1
    So,

X + X = 2X = X &laquo_space;1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Bit Tricks:

Multiplying by a power of 2:

X*(2^n)

A

Multiplying by 2 is equivalent to an Arithmetic Left Shift of 1.
2X = X &laquo_space;1

So, multiplying X by 2 n times is the same as shifting X n times

X*(2^n) = X &laquo_space;n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Bit Identities:

X ^ ~X = ?

A

X XOR (NOT X)

X ^ ~X = 1s

For a bit in X:
If 1, 1 ^ 0 = 1
If 0, 0 ^ 1 = 1

All bits are set to 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the typical representation of signed integers called?

A

Two’s Complement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is Two’s Complement?

A
  • How signed integers are usually stored
  • The most significant bit indicates if a number is positive or negative
  • The remaining bits store the value of the number
  • Positive numbers store the value normally
  • Negative numbers are stored as:
    2^(N-1) - K
    Where N is the number of bits used( eg, 8, 16, 32, 64)
    and K is the absolute value of the integer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Two’s Complement:
How are positive integers stored?

A
  • The first bit is 0, indicating a positive number
  • The remaining bits are the binary representation of the number

Example: In a 4-bit system

1 -> 0 001
2 -> 0 010

21
Q

Two’s Complement:
How are Negative Integers stored?

A
  • The most significant bit is a 1 to indicate a negative value
  • The absolute value of the number(K) is subtracted from 2^N,
    where N is the number of bits, not including the sign bit

Example: In a 4-bit system
2^N = 2^3
The binary representation of 2^3 = 1000

-1 is represented by 1 [1000 - 001] = 1 [111]
so, -1 = 1111 in Two’s Complement

-2 = 1 [1000 - 010] = 1 [110]

22
Q

Two’s Complement:
Maximum Absolute Value of integers stored in an N-bit system

A

2^(N-1) - 1
An N-bit system has N-1 bits to store the absolute value,
as one bit is always used for the sign bit

23
Q

Two’s Complement:
Converting a positive integer to a negative

A
  • Start with the positive representation
    3 -> 011
  • Perform NOT operation to “flip” the number
    ~3 -> 100
  • Add 1
    101
  • Prepend the sign bit
    -3 = 1101
24
Q

Two’s Complement:
Relationship between positive and negative integers

A

Every positive integer has a negative counterpart,
where the absolute values ALWAYS sum to 2^(N-1)

Example: in a 4-bit system:

1: 0001
-1: 1111

001 + 111 = 1000 = 2^3

2: 0010
-2: 1110

010 + 110 = 1000 = 2^3

This is why it’s called “Two’s Complement”

25
Q

What is the Two’s Complement binary value of:
7

A

0 111

26
Q

What is the Two’s Complement binary value of:
6

A

0 110

27
Q

What is the Two’s Complement binary value of:
5

A

0 101

28
Q

What is the Two’s Complement binary value of:
4

A

0 100

29
Q

What is the Two’s Complement binary value of:
3

A

0 011

30
Q

What is the Two’s Complement binary value of:
2

A

0 010

31
Q

What is the Two’s Complement binary value of:
1

A

0 001

32
Q

What is the Two’s Complement binary value of:
0

A

0 000

33
Q

What is the Two’s Complement binary value of:
-1

A

1 111

34
Q

What is the Two’s Complement binary value of:
-2

A

1 110

35
Q

What is the Two’s Complement binary value of:
-3

A

1 101

36
Q

What is the Two’s Complement binary value of:
-4

A

1 100

37
Q

What is the Two’s Complement binary value of:
-5

A

1 011

38
Q

What is the Two’s Complement binary value of:
-6

A

1 010

39
Q

What is the Two’s Complement binary value of:
-7

A

1 001

40
Q

Bitwise Operators:
Difference between
Arithmetic Right Shift (»)
and
Logical Right Shift (»>)

A

Arithmetic Right shift maintains the sign bit and fills in the new bits with whatever the original sign bit is.

Logical Shift does NOT maintain the sign bit,
always fills in the new bits with 0

41
Q

Bitwise Operators:
Arithmetic Right Shift
x&raquo_space; n

A
  • Shifts all bits to the right, n times
  • Fills in new bits with the sign bit:
    0 if positive number
    1 if negative number
  • Equivalent to dividing by 2, n times.

Examples:
4&raquo_space; 2:
0 100&raquo_space; 2 = 0 001 = 1
-4&raquo_space; 2:
1 100&raquo_space; 2 = 1 111 = -1

42
Q

Bitwise Operators:
Logical Right Shift
X&raquo_space;> n

A
  • Shifts all bits to the right, n times
  • Fills in new bits with 0
  • Does NOT preserve sign bit
  • On positive numbers, equivalent to Arithmetic Right Shift

Example:
5&raquo_space;> 1:
0 101&raquo_space;> 1 = 0 010 = 2

-2&raquo_space; 1:
1 110&raquo_space;> 1 = 0 111 = 7

43
Q

Most common tasks of bit manipulation

A
  • Get Bit
  • Set Bit
  • Clear Bit
    • Clear all bits from i to the left
    • Clear all bits from i to the right
    • Clear bits from i to j
  • Update a bit
44
Q

Common Bit Tasks:
Get Bit

A

Goal:
Check if the ith bit of a number is 1 or 0

How:
* Create a mask by shifting 1 (0001) left to the ith position:
1 &laquo_space;i

  • AND the mask with the number
    • If result is not 0, the ith bit is a 1, else it is 0
  • Because only the ith bit of the mask is 1, only the ith bit of the number affects the result.

example:
Check bit 2 of 0101:
mask = 1 &laquo_space;2 = 0001 &laquo_space;2 = 0100

0101 & 0100 = 0100
45
Q

Common Bit Tasks:
Set Bit

A

Goal:
Set the ith bit of a number to 1

How:
* Create a mask by shifting 1(0001) to the left to the ith position
1 &laquo_space;i
* OR with the number
* The result is exactly the same as the number, except for the ith bit
* If bit i was already 1, it is the same

Example:
Set bit 2 of 1010:
mask = 1 &laquo_space;2 = 0100

1010 | mask = 1010 | 0100 = 1110

46
Q

Common Bit Tasks:
Clear Bit

A

Goal:
Clear the ith bit (set to 0)

How:
* Create a sort of reverse mask:
Shift 1 by i, then negate it
mask = 0001 &laquo_space;2 = 0100
nMask = ~mask = 1011
* AND this mask with the number. The ith bit will be 0, the other bits will remain the same.

Example:
Clear bit 2 of 1101:
result = 1101 & ~(1 &laquo_space;2) = 1001

47
Q

Common Bit Tasks:
Clear Bits to the Left

A

Goal:
Clear all bits from the Most Significant Bit to i

How:
* Create a bitmask that is all 1s until i, and 0s from i to MSB
- Shift 1 by i
- Subtract 1
* AND bitmask with number
* Result leaves only bits 0 to i

Example:
Clear bits to left of bit 3 on 1010 1101
Create bitmask:
1 &laquo_space;3 = 0000 1000
Subtract 1
0000 0111
AND with Number:
1010 1101
&0000 0111
——————
= 00000111

48
Q

Common Bit Tasks:
Clear all bits to the right

A

Goal:
Clear all bits from 0 to i (right of i, inclusive)

How:
* Create a bitmask that is all 0s from 0 to i, then 1s from i+1 to MSB
* Shift -1 to the left by i+1:
* -1 is always all 1s in two’s complement representation
* AND with the target

Example:
Clear bits to right of bit 3 on 1010 1101
Create bitmask:
-1 &laquo_space;3+1 = 1 111 1111 &laquo_space;4 = 1 111 0000

AND with Number:
1010 1101
&1111 0000
——————
= 1010 0000

Cracking the Coding Interview (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions