Bitwise

Table of Contents

Bitwise AND

Think of bitwise AND like a hose with two knobs. Both knobs must be set to "on" for water to come…

The AND operation takes two bits and returns 1 if both bits are 1. Otherwise, it returns 0.

1 & 1 → 1
1 & 0 → 0
0 & 1 → 0
0 & 0 → 0

Think of it like a hose with two knobs. Both knobs must be set to on for water to come out.

When performing AND on two integers, the AND operation is calculated on each pair of bits (the two bits at the same index in each number).

5 & 6     # gives 4

# At the bit level:
#         0101  (5)
#       & 0110  (6)
#       = 0100  (4)

BitWise OR

Think of bitwise OR like a bucket with two holes in it. If both holes are closed, no water comes ou…

The OR operation takes two bits and returns 1 if either of the bits are 1. Otherwise, it returns 0.

1 | 1 → 1
1 | 0 → 1
0 | 1 → 1
0 | 0 → 0

Think of it like a bucket with two holes in it. If both holes are closed, no water comes out. If either hole is open, or if both are open, water comes out.

When performing OR on two integers, the OR operation is calculated on each pair of bits (the two bits as the same index in each number).

5 | 6    # gives 7

# At the bit level
#         0101 (5)
#       | 0110 (6)
#       = 0111 (7)

Bitwise XOR (eXclusive OR)

The XOR operation (or exclusive or ) takes two bits and returns 1 if exactly one of the bits is 1. Otherwise, it returns 0.

1 ^ 1  →  0
1 ^ 0  →  1
0 ^ 1  →  1
0 ^ 0  →  0

Think of it like a bag of chips where only one hand can fit in at a time. If no one reaches for chips, no one gets chips, and if both people reach for chips, they can't fit and no one gets chips either!

When performing XOR on two integers, the XOR operation is calculated on each pair of bits (the two bits at the same index in each number).

5 ^ 6     # gives 3

# At the bit level:
#         0101  (5)
#       ^ 0110  (6)
#       = 0011  (3)

Bitwise NOT

Bitwise NOT basically "flips" the set of bits you give it, changing all the 1s to 0s and all the 0s…

The NOT bitwise operation takes one set of bits, and for each bit returns 0 if the bit is 1, and 1 if the bit is 0.

~ 0 → -1
~ 1 → -2

When performing NOT on an integer, each bit of the integer is inverted.

~ 5       # gives -6

# At the bit level:
#  ~ 0000 0101  (5)
#  = 1111 1010  (-6)

If you're unsure why the resulting number is negative in this example, it's because numbers are represent using two's complement. Read up on binary numbers here.

Bit Shifting

A bit shift moves each digit in a set of bits left or rigt. The last bit in the direction of the s…

A bit shift moves each digit in a number's binary representation left or right. There are three main types of shifts:

Left Shifts

When shifting left, the most-significant bit is lost, and a 0 bit is inserted on the other end.

The left shift operator is usually written as "<<".

0010 << 1  →  0100
0010 << 2  →  1000

A single left shift multiplies a binary number by 2:

0010 << 1  →  0100

0010 is 2
0100 is 4

Logical Right Shifts

When shifting right with a logical right shift , the least-significant bit is lost and a 0 is inserted on the other end.

1011 >> 1  →  0101
1011 >> 3  →  0001

For positive numbers, a single logical right shift divides a number by 2, throwing out any remainders.

0101 >> 1  →  0010

0101 is 5
0010 is 2

Arithmetic Right Shifts

When shifting right with an arithmetic right shift , the least-significant bit is lost and the most-significant bit is copied.

Languages handle arithmetic and logical right shifting in different ways. Python's right shift operator (>>) always does arithmetic right shifting.

1011 >> 1  →  1101
1011 >> 3  →  1111

0011 >> 1  →  0001
0011 >> 2  →  0000

The first two numbers has a 1 as the most significant bit, so more 1's were inserted during the shift. The last two numbers had a 0 as the most significant bit, so the shift inserted more 0's.

If a number is encoded using two's complement, then an arithmetic right shift preserves the number's sign, while a logical right shift makes the number positive.

# Arithmetic shift
1011 >> 1  →  1101
    1011 is -5
    1101 is -3

# Logical shift
# (Not a thing in Python, but if it were:)
1111 >> 1  →  0111
    1111 is -1
    0111 is  7

Date: 2020-01-31 Fri 15:15

Author: Jack Liu

Created: 2020-02-08 Sat 21:25

Validate