Brainscape's Knowledge GenomeTM

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


See full index

Coding Interviews > Binary Numbers and Bit Manipulation > Flashcards

Binary Numbers and Bit Manipulation Flashcards

1
Q

What does the bitwise AND (&) operator do?

A

The AND operator takes two bits and returns 1 if both bits are 1, otherwise returns 0 Think of it like a hose with two knobs – both knobs must be set to on for water to come out (for 1 to return)

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

2^2

A

4

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

1 & 0

A

0

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

~ 0000

A

0000 (0) becomes 1111 (15)

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

What does the bitwise XOR (^) operator do?

A

XOR or exclusive or takes two bit and returns 1 if exactly one of the bits is 1, otherwise it returns 0 Think of it like a bag of chips where only one hand can fit. If no one reaches for chips no one gets chips, if both people reach for chips, they can’t fit and no one gets chips either

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

0011 >> 2 (arithmetic right shift)

A

0000 (sig digit 0 copied 2 times)

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

0010 << 2

A

1000

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

0 | 1

A

1

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

1011 >> 1 (arithmetic shift, two’s complement)

A

1011 (-8 + 0 + 2 + 1 = -5) 1101 (-8 + 4 + 0 + 1 = -3)

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

0 & 1

A

0

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

Bit manipulation when you want to cancel out matching numbers?

A

XOR

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

What happens in an arithmetic right shift?

A

The least significant bit is lost and the most significant bit is copied N number of shifts

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

Binary to decimal: 1011 in two’s complement

A

-8 + 0 + 2 + 1 = -5

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

1011 >> 1 (arithmetic right shift)

A

1101 (sig digit 1 copied 1 time)

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

0101 & 0110

A

0100

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

What is two’s complement encoding?

A

In two’s complement, the leftmost digit is negative, and the rest of the digits are positive. ex: 101 = -4 + 0 + 1 = -3

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

What happens if a number is encoded using two’s complement and arithmetic right shifted?

A

The number sign is preserved (negative stays negative)

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

Binary to Decimal: 1001

A

8 + 0 + 0 + 1 = 9

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

What is a bit shift?

A

Moving each digit in a number’s binary representation left or right

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

Binary to decimal: 1001 in two’s complement

A

-8 + 0 + 0 + 1 = -7

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

~ 0101

A

0101 (5) becomes 1010 (10)

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

Binary to Decimal: 0101

A

0 + 4 + 0 + 1 = 5

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

What happens to the value of a binary number with a single left shift?

A

Multiplies the binary number by 2 ex: 0010 << 1 becomes 0100 (2 to 4)

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

Binary to Decimal: 0111

A

0 + 4 + 2 + 1 = 7

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

What does python’s right shift operator (>>) always do?

A

Arithmetic right shifting

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

Binary to Decimal: 0110

A

0 + 4 + 2 + 0 = 6

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

What does the bitwise OR (|) operator do?

A

The OR operator takes two bits and returns 1 if either of the bits are 1. Otherwise it returns 0 Think of it as a bucket with two holes. If both holes are closed, no water comes out. If either hole is open or if both are open, water comes out (returns 1)

28
Q

What happens to the value of a binary number with a single logical right shift?

A

Divides the binary number by 2, throwing out any remainders ex: 0101 >> 1 becomes 0010 (5 becomes 2)

29
Q

1 ^ 0

A

1

30
Q

0 & 0

A

0

31
Q

0101 ^ 0110

A

0011

32
Q

What does the bitwise NOT (~) operator do?

A

The NOT bitwise operator inverts bits. A 0 becomes 1 and a 1 becomes 0.

33
Q

2^0

A

1

34
Q

2^1

A

2

35
Q

5 | 6

A

0101 (5) | 0110 (6) ———— 0111 (7)

36
Q

1 | 0

A

1

37
Q

0011 >> 1 (arithmetic right shift)

A

0001 (sig digit 0 copied 1 time)

38
Q

0010 << 1

A

0100

39
Q

0 | 0

A

0

40
Q

What happens in a logical right shift?

A

The least significant bit is lost and a 0 is inserted on the other end

41
Q

1 ^ 1

A

0

42
Q

1 | 1

A

1

43
Q

Binary to Decimal: 1000

A

8 + 0 + 0 + 0 = 8

44
Q

2^3

A

8

45
Q

1011 >> 3 (arithmetic right shift)

A

1111 (sig digit 1 copied 3 times)

46
Q

Bit manipulation when you want to divide by 2?

A

Right shift 6 >> 1 0110 >> 1 = 0011 (3)

47
Q

What happens in a left shift?

A

The most significant bit is lost and a 0 bit is inserted on the other end

48
Q

1011 >> 3

A

0001

49
Q

What happens if a number is encoded using two’s complement and is logical right shifted?

A

The number becomes positive

50
Q

Bit manipulation when you want to multiply by 2?

A

Left shift 6 << 1 0110 << 1 = 1100 (12)

51
Q

1011 >> 1

A

0101

52
Q

0 ^ 0

A

0

53
Q

0 ^ 1

A

1

54
Q

1 & 1

A

1

55
Q

Binary to Decimal: 1010

A

8 + 0 + 2 + 0 = 10

56
Q

What are the 3 types of bit shifts?

A

Left Shift Logical Right Shift Arithmetic Right Shift

57
Q

Converting number in to bits

A

base = 2

while num > 0:

remainder = n%base

0

58
Q

How to convert positive representation of a number to two’s complement

A

Invert the bits, add 1 and prepend 1

ex:

  1. 3 is 011 in binary
  2. ~011 inverted is 100
  3. add 001 (1) is 101
  4. prepend 1 is 1101 (-8 + 4 + 0 + 1 = -3)
59
Q

Psuedo-code for getting a bit at i

A
  1. Create mask by shifting 1 over by i bits (ex: 0001000)
  2. AND the mask with the number (clearing out all bits except at i)
  3. If the result is 0, then i was 0, if any other number then i was 1
60
Q

Psuedo-code for setting a bit at i

A
  1. Create a mask by shifting 1 over by i bits
  2. Perform an OR with the mask and number
  3. Only the bit at i will change
61
Q

What does AND with this mask do? 0001000

A

Clear out all bits except at i

62
Q

What does OR with this mask do? 0001000

A

Changes only the bit at i

63
Q

How do you create a mask that looks like this? 1110111

A
  1. Left shift 1 to i
  2. Perform NOT (~) operator
64
Q

Psuedocode for clearing a bit at i

A
  1. Create a mask with 0 at i bit e.g.: ~(1 << i)
  2. AND the mask with the number
65
Q

Psuedocode for updating a bit

A
  1. Clear the bit at i by using a mask 1110111 and AND it with the number
  2. Create a new mask left shifting the new value to i (0001000)
  3. OR the result from 1 with the new mask
66
Q

How do you go from a positive value to it’s inverse in two’s complement (ex: 5 to -5)

A
  1. Invert the bit (~0101 = 1010)
  2. Add 1 (1010 + 0001 = 1011)
  3. 1011 = -8 + 0 + 2 + 1 = -5
67
Q

How do you go from a negative value to it’s inverse in two’s complement (ex: -7 to 7)

A
  1. Invert the bit (~1001 = 0110)
  2. Add 1 (0110 + 0001 = 0111)
  3. 0111 = -0 + 4 + 2 + 1 = 7

Coding Interviews (10 decks)

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