FAQ of Bitwise Manipulation and their Semantics

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.

def getLeastSignificantSetBit(num :int):
result = num & (-num)
return result
E.g. num == 4, i.e. 0b000…0100.
-4 or -num is 0b111...1100
result returns 0b000...0100
n&(n-1) will remove the rightmost in binary representation of n. 
For example if n = 10110100, then n & (n-1) = 10110100 & 10110011 = 10110000,
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
def isPowerOfTwo(self, n: int) -> bool:
return n & (n-1) == 0 # 100 & 011 == 0
# explaination: e.g. 0100 & 0011 == 0
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.
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]]

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store