Bitwise operators

Bitwise operations allow you to manipulate data at a binary level. Remember that all data is represented by binary numbers under the hood.

For example, the binary representation of the decimal number 5 is 0101.

What are Binary Numbers?

We can derive the decimal version of a binary number by summing each bit's position as the exponent of 2, where position 0 is the right-most bit, or the least significant bit.

So 0101 = (0 * 2³) + (1 * 2²) + (0 * 2¹) + (1 * 2⁰) = 0 + 4 + 0 + 1 = 5

Bitwise AND: &

The bitwise AND (&) of two numbers is a comparison of each bit in the same position of the input numbers, and is 1 only if both bits in that position are 1.

AND Truth Table

A	B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

Bitwise AND in Python

a = 5
b = 3
result = a & b

print('a = decimal: ', a, ' = binary: ', f'{a:04b}')
print('b = decimal: ', b, ' = binary: ', f'{b:04b}')
print('a & b = decimal: ', result, ' = binary: ', f'{result:04b}')

1a = 5
2b = 3
3result = a & b
4
5print('a = decimal: ', a, ' = binary: ', f'{a:04b}')
6print('b = decimal: ', b, ' = binary: ', f'{b:04b}')
7print('a & b = decimal: ', result, ' = binary: ', f'{result:04b}')
8

Bitwise OR: |

The bitwise OR (&) of two numbers is 1 in corresponding bit positions if either bit is 1, and 0 if both bits are 0.

OR Truth Table

`A`	`B`	`A \| B`
0	0	0
0	1	1
1	0	1
1	1	1

Bitwise OR in Python

a = 7
b = 2
result = a | b

print('a = decimal: ', a, ' = binary: ', f'{a:04b}')
print('b = decimal: ', b, ' = binary: ', f'{b:04b}')
print('a | b = decimal: ', result, ' = binary: ', f'{result:04b}')

1a = 7
2b = 2
3result = a | b
4
5print('a = decimal: ', a, ' = binary: ', f'{a:04b}')
6print('b = decimal: ', b, ' = binary: ', f'{b:04b}')
7print('a | b = decimal: ', result, ' = binary: ', f'{result:04b}')
8

Bitwise XOR: ^

The bitwise XOR (^), or exclusive or of two numbers is 1 in corresponding bit positions only if the bits differ. Otherwise the output is 0.

XOR Truth Table

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

XOR Tricks

The XOR operation has some neat properties that make it useful for solving some coding interview problems.

XOR operations are commutative, which means the ordering of the operations do not matter: a ^ b ^ c = c ^ a ^ b
A number XOR with itself is always 0: a ^ a = 0.
A number XOR with 0 is the number itself: a ^ 0 = a.

For example, let's consider the problem of finding the missing number in a given array of numbers 1..n, but is missing one number from that range.

One way to find the missing number is to use all 3 XOR properties above and do the following:

XOR every number in the input array
XOR the result with each number from the range 1..n.
The remaining number is the missing number.

XOR operations in Python

a = 9
b = 12
result = a ^ b

print('a = decimal: ', a, ' = binary: ', f'{a:04b}')
print('b = decimal: ', b, ' = binary: ', f'{b:04b}')
print('a ^ b = decimal: ', result, ' = binary: ', f'{result:04b}')
print('\n')

print('XOR is commutative')
print(a ^ b, ' is the same as ', b ^ a)
print('\n')

print('An integer XOR with 0 always returns the number itself')
print('a ^ 0 = ', a ^ 0)
print('b ^ 0 = ', b ^ 0)

print('An integer XOR with witself always returns 0')
print('a ^ a = ', a ^ a)
print('b ^ b = ', b ^ b)

1a = 9
2b = 12
3result = a ^ b
4
5print('a = decimal: ', a, ' = binary: ', f'{a:04b}')
6print('b = decimal: ', b, ' = binary: ', f'{b:04b}')
7print('a ^ b = decimal: ', result, ' = binary: ', f'{result:04b}')
8print('\n')
9
10print('XOR is commutative')
11print(a ^ b, ' is the same as ', b ^ a)
12print('\n')
13
14print('An integer XOR with 0 always returns the number itself')
15print('a ^ 0 = ', a ^ 0)
16print('b ^ 0 = ', b ^ 0)
17
18print('An integer XOR with witself always returns 0')
19print('a ^ a = ', a ^ a)
20print('b ^ b = ', b ^ b)
21

Bitwise Complement: ~

The bitwise Complement (~) flips all the bits of the single input number.

Bitwise Complement in Python

x = 12
print('decimal: ', x, ' binary: ', f'{x:08b}')
y = ~x
print('Bitwise Complement:')
print('decimal: ', y, ' binary: ', f'{y:08b}')

1x = 12
2print('decimal: ', x, ' binary: ', f'{x:08b}')
3y = ~x
4print('Bitwise Complement:')
5print('decimal: ', y, ' binary: ', f'{y:08b}')
6

Twos complement numbers

To support signed integers, Python uses twos complement numbers.

Twos complement numbers implies that For numbers greater than or equal to 0 are represented by its regular binary representation ( 3 = 0011).

Negative numbers are represented with the most significant bit set to 1.

For example, to get the binary representation of -14, working with an 8-bit integer:

Start with the absolute value of the input: 14, or in binary form 0000 1110.
Flip each bit - 1 becomes 0, and 0 becomes 1: 1111 0001
Add 1 to that 1111 0010

So twos complement binary numbers can represent both positive and negative numbers.

Remember, in twos complement binary numbers, one bit is occupied to determine the sign of the number, so an 8-bit integer can really only hold 7 bits of information.

So the max value a signed 8-bit integer can hold is 127.

Bitwise Left Shift: <<

A bitwise left shift takes a binary number and literally shifts all the bits to the left, and adds a 0 in the least significant bit positions.

For example:

0101 << 1 = 1010 # same as 5 << 1 = 5 * 2 = 10
0001 << 3 = 1000 # same as 1 << 3 = 1 * 8 = 8

Let's say the shift amount is X. You can see that left shifts are the same as multiplying an input number by 2^X

Bit Shifting tricks

Shifting along with the AND operation can be used to create a bit mask, which is a way to extract specific bits from a number.

For example, shifting 1 to the second digit, and applying a bitwise AND to the bit mask and a number would extract the second bit of the input number.

Left shifts in Python

a = 7
b = 2
result = a << b

print('a = decimal: ', a, ' = binary: ', f'{a:04b}')
print('a << b = decimal: ', result, ' = binary: ', f'{result:04b}')
print('\n')

# bit masking
bit_mask = 1 << 1
result = a & (1 << 1)
print('2nd least significant bit mask = ', f'{bit_mask:04b}')
print('extract 2nd least significant bit: a & bit_mask', f'{result:04b}')

1a = 7
2b = 2
3result = a << b
4
5print('a = decimal: ', a, ' = binary: ', f'{a:04b}')
6print('a << b = decimal: ', result, ' = binary: ', f'{result:04b}')
7print('\n')
8
9# bit masking
10bit_mask = 1 << 1
11result = a & (1 << 1)
12print('2nd least significant bit mask = ', f'{bit_mask:04b}')
13print('extract 2nd least significant bit: a & bit_mask', f'{result:04b}')
14

Bitwise Right Shift: >>

A bitwise right shift takes a binary number and shifts all the bits to the right by a specified amount, and adds a 0 in the most significant bit positions.

For example:

1000 >> 2 = 0010 # same as 8 >> 2 = 8 / 4 = 2
0101 >> 1 = 1010 # same as 5 >> 1 = 5 / 2 = 2

Again, let's say the shift amount is X. You can see that right shifts are the same as dividing an input number by 2^X

Note that the division of odd numbers by any factor of 2 results in some remainder. This is essentially lost in a bitwise right shift.

Therefore, bitwise right shifts actually apply floor division to a number.

Right shifts in Python

result = 7 >> 1
print('7 >> 1 = ', result)
print(f'{7:04b}', ' >> 1 = ', f'{result:04b}')

1result = 7 >> 1
2print('7 >> 1 = ', result)
3print(f'{7:04b}', ' >> 1 = ', f'{result:04b}')
4

6 Essential Primitives Coding Interview Problems

Master Primitives by trying the coding challenges below.

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.