FAQ of Bitwise Manipulation and their Semantics
2 min readSep 15, 2022
I am bad at bitwise operations. So what better way then to create an aide memoir of my learnings. I will update as life goes along.
Given an array with two repeated numbers and one single number, how to find the single number using XOR?
e.g. array = [4, 4, 8]def findSingleNumber(array): result = 0
for num in array:
result ^= num
return result Output of findSingleNumber([4, 4, 8]) will be 8.
The above works, because an xor of two repeated number will be zero. And zero xor with the single number will be the single number. Key here is xor will only be 1 when the two xor-ed bits are clear and set bits.
How to find the least significant set bit?
def getLeastSignificantSetBit(num :int):
result = num & (-num)
return resultE.g. num == 4, i.e. 0b000…0100.
-4 or -num is 0b111...1100
result returns 0b000...0100
How to remove the rightmost set bit or the least significant set bit?
n&(n-1) will remove the rightmost in binary representation of n.
For example if n = 10110100, then n & (n-1) = 10110100 & 10110011 = 10110000,
How do you reverse a bit string (represented by a 32 bit unsigned integer) fast?
def reverseBits(self, n: int) -> int:
result = 0
for i in range(32):
result = (result << 1) |(n & 1) # push from left
# to right using n //= 2 # pop from left return result
How to check if a positive integer number n is of power of two fast?
def isPowerOfTwo(self, n: int) -> bool:
return n & (n-1) == 0 # 100 & 011 == 0# explaination: e.g. 0100 & 0011 == 0
How do you generate a fixed length bitmask from 0…00 to 1…000 in Python? What is the use?
for i in range(2**length, 2**(length+1)):
bitmask = bin(i)[3:]# Above code generate bit mask 0..00 to 1..11
# E.g. if length == 3: 2**3 is 1000 and
# 2**4 - 1 is 1111 (2**4 is 10000).
# The function call bin(i) produces binary string of "0b1000" to
# "0b1111",so bin(i)[3:] removes prefix "0b1" to give us the fixed #
# length(3) bitmask.
What is the use? — Creating a Power Set from a list of integers.
from typing import Listclass Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
powerSet = []
length = len(nums) for i in range(2**length, 2**(length+1)): bitmask = bin(i)[3:]
aSet = []
for j in range(length):
if bitmask[length - j - 1] == "1":
aSet.append(nums[j])
powerSet.append(aSet) return powerSetnums = [1,2,3]
Ouput = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]