Python Bitwise Operators

[qingquan-li]

Python Bitwise Operators

Bitwise operators are used to compare (binary) numbers:

Operator	Name	Description	Example
&	AND	Sets each bit to 1 if both bits are 1	x & y
|	OR	Sets each bit to 1 if one of two bits is 1	x | y
^	XOR	Sets each bit to 1 if only one of two bits is 1	x ^ b
~	NOT	Inverts all the bits	~x
<<	Zero fill left shift	Shift left by pushing zeros in from the right and let the leftmost bits fall off	x << 2
>>	Signed right shift	Shift right by pushing copies of the leftmost bit in from the left, and let the rightmost bits fall off	x >> 2

& (AND) Operator

The & (bitwise AND) operation compares each bit of two numbers and results in 1 if both bits are 1, and 0 otherwise.

Example 1:

a = 8      # 1000
b = 9      # 1001
c = a & b  # 1000
print(c)   # 8

Example 2:

Please create a function is_power(arr) to do the following: Given an array of integers, determine whether each is a power of 2, where powers of 2 are [1, 2, 4, 8, 16, 32, 64,...]. For each integer evaluated, append to an array a value of 1 if the number is a power of 2, or 0 otherwise.

For example: arr = [1, 3, 8, 12, 16] 1 = 2^0, 8 = 2^3, and 16 = 2^4. The return array is [1, 0, 1, 0, 1].

Step 1 - Understand

1 in binary: 1 2 in binary: 10 4 in binary: 100 8 in binary: 1000 And so on...

In each case, subtracting 1 from the number will flip all the bits after the first set bit, making the bitwise AND operation result in zero.

1-1 = 0 in binary: 0 2-1 = 1 in binary: 01 4-1 = 3 in binary: 011 8-1 = 7 in binary: 0111 And so on...

Therefore, the condition n & (n−1) == 0 is used to check if a number is a power of 2. Example: 8 = 1000, 8-1 = 7 = 0111, 8 & 7 = 0.

Step 2 - Plan:

1. Iterate over the input array.
2. For each number, check if it satisfies the condition n & (n−1) == 0 and n > 0.
3. Append 1 to the result if it is a power of 2, otherwise append 0.

Step 3 - Implement

def is_power(arr):
    result = []
    for num in arr:
        if num > 0 and (num & (num - 1)) == 0:
            result.append(1)
        else:
            result.append(0)
    return result


arr = [1, 3, 8, 12, 16]
print(is_power(arr))  # [1, 0, 1, 0, 1]

Time complexity: O(n), where n is the number of elements in the input array. Space complexity: O(n), where n is the number of elements in the input array.

Use a "traditional" approach to check if a number is a power of 2

Time complexity: O(n log k), where n is the length of the array and k is the largest number in the array. Space complexity: O(n), where n is the length of the array.

def is_power(arr):
    result = []
    for num in arr:
        if num > 0:
            while num % 2 == 0:
                num /= 2
            if num == 1:
                result.append(1)
            else:
                result.append(0)
        else:
            result.append(0)
    return result

| (OR) Operator

The | (bitwise OR) operation compares each bit of two numbers and results in 1 if either of the bits is 1, and 0 otherwise.

Example:

a = 8      # 1000
b = 9      # 1001
c = a | b  # 1001
print(c)   # 9

^ (XOR) Operator

The ^ (bitwise XOR) operation compares each bit of two numbers and results in 1 if only one of the bits is 1, and 0 otherwise.

Example:

a = 8      # 1000
b = 9      # 1001
c = a ^ b  # 0001
print(c)   # 1

~ (NOT) Operator

The ~ (bitwise NOT) operation inverts all the bits of a number.

Example:

a = 8     # 0000 1000
b = ~a    # 1111 0111 -> 0000 1000 + 0000 0001 = 0000 1001
print(b)  # -9
a = 9     # 0000 1001
b = ~a    # 1111 0110 -> 0000 1001 + 0000 0001 = 0000 1010
print(b)  # -10

<< (Zero fill left shift) Operator

The << (left shift) operator shifts the bits of a number to the left by a specified number of positions. Zeros are shifted in from the right, and the leftmost bits fall off.

Example:

a = 8       # 0000 1000
b = a << 2  # 0010 0000
print(b)    # 32
a = 9       # 0000 1001
b = a << 2  # 0010 0100
print(b)    # 36

>> (Signed right shift) Operator

The >> (right shift) operator shifts the bits of a number to the right by a specified number of positions. Copies of the leftmost bit are shifted in from the left, and the rightmost bits fall off.

Example 1:

a = 8       # 1000
b = a >> 2  # 0010
print(b)    # 2
a = 9       # 1001
b = a >> 2  # 0010
print(b)    # 2

Example 2:

Java ArrayList - Internal Implementation:

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

When the ArrayList is full, the capacity is increased by 50%:

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

Explanation:

oldCapacity = 10 (1010 in binary) oldCapacity >> 1 = 5 (0101 in binary) newCapacity = 10 + 5 = 15 (1111 in binary)

oldCapacity = 15 (1111 in binary) oldCapacity >> 1 = 7 (0111 in binary) newCapacity = 15 + 7 = 22 (10110 in binary)