Bit Manipulation Questions
from functools import reduce, partial from operator import xor, and_
Hamming Distances / Bit counting.
191. Number of 1 Bits
Write a function that takes an unsigned integer and return the number of ‘1’ bits it has (also known as the Hamming weight.
x & (x - 1)clear the last bit.
- we count the number of bits we need to clear to zero out the number.
def hamming_weight(n): c = 0 while n: n &= (n - 1) c += 1 return c
461. Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
- XOR gives the bit difference.
- Once we get the difference, we use the above technique to count number of 1 bits.
def hamming_distance(x, y): diff = x ^ y distance = 0 while diff: distance += 1 diff &= (diff - 1) return distance
477. Total Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance between all pairs of the given numbers.
- Iterative over all possible pairs is \(N^2\).
- Count the number of 0 and 1 at each bit, then the total difference from that bit is the product of the two frequencies.
(num & 1 << i) == 0checks the ith bit is 1 or not.
def total_hamming_distance(nums): bits = [[0, 0] for _ in range(32)] for num in nums: for i in range(32): if (num & 1 << i) == 0: bits[i] += 1 else: bits[i] += 1 return sum(x * y for x, y in bits)
338. Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
i & (i - 1)clears the last bit of given number.
iis a larger number than
i - 1and
icontains one more bit than
i - 1.
- So we have the recurrsive relation ship
num_bits(i) = num_bits(i & (i - 1)) + 1.
def count_bits(num): solution =  * (num + 1) for i in range(1, num + 1): solution[i] = solution[i & (i - 1)] + 1 return solution
405. Convert a Number to Hexadecimal
Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.
- Every four consecutive bits from right corresponds to a single digit in hex decimal right the right.
x & 15will extract the last four bits from x.
- We just do convertion one digit at a time.
def to_hex(num): digits =  for i in range(8): digits.append('0123456789abcdef'[num & 15]) num = num >> 4 return ''.join(digits)[::-1].lstrip('0') or '0'
371. Sum of Two Integers
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
- XOR gives the remainder.
&gives the carry which needs to be shifted to left.
while b: a, b = a ^ b, (a & b) << 1is the workhorse to do addition.
- Note python’s binary number has sign, instead of using two’s complement, we need the mask to loss the sign in the loop, and in the end get the sign back.
- To do so, let mask be the all 1 bitmask,
& maskwill cause the negative number to become two’s complement.
~(x ^ mask)will conver the number back to negative.
def get_sum(a, b): mask = (1 << 32) - 1 while b: xor = a ^ b carry = (a & b) << 1 a, b = xor & mask, carry & mask return a if a <= (1 << 31) - 1 else ~(a ^ mask)
268. Missing Number
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
x ^ x == 0and
x ^ 0 == x.
- We loop over 0 to n once accumulate the xors, then loop over nums to cancel the pairs.
- The remainder is the missing number.
def missing_number(nums): return reduce(xor, list(range(len(nums) + 1)) + nums)
136. Single Number
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
x ^ x == 0, so the number with frequency two will cancer each other.
0 ^ x == x, so we can use 0 as default in reduction if nums contains only one number.
def single_number(nums): return reduce(xor, nums, 0)
137. Single Number II
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
- Main workhorse is still xor,
x ^ x == 0and
0 ^ x == 0.
- The trick is we need to use seperate masks for bit flipping.
|once ^ num||010||once ^ num||000||once ^ num||010|
|~twice & (once ^ num)||010||~twice & (once ^ num)||000||~twice & (once ^ num)||000|
|twice ^ num||010||twice ^ num||010||twice ^ num||000|
|~once & (twice ^ num)||000||~once & (twice ^ num)||010||~once & (twice ^ num)||000|
def single_number_ii(nums): once = twice = 0 for num in nums: once = ~twice & (once ^ num) twice = ~once & (twice ^ num) return once
260. Single Number III
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
- find the difference between the two single numbers with xor.
x & ~(x - 1)or other alternative can extract the last bit from a number.
- This last bit must exsit in one and only one of the the two numbers.
- We can filter the numbers with by this last bit.
- Use xor reduction on the filtered numbers, we can recover one of the single number.
diff ^ xwill seperate out the second number from the diff.
def single_number_iii(nums): diff = reduce(xor, nums) lsb = diff & ~(diff - 1) x = reduce(xor, filter(partial(and_, lsb), nums)) return [x, diff ^ x]
Given a set of distinct integers, nums, return all possible subsets (the power set).
[bin(i) for i in range(1 << length)]will give a permutation map for sequence of given length.
- For each permutation we iterate over the elements and ensemble them according to the permutation.
def subsets(nums): subsets =  for i in range(1 << len(nums)): subset =  for j, num in enumerate(nums): if i & (1 << j): subset.append(num) subsets.append(subset) return subsets
784. Letter Case Permutation
Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.
- For each permutation, we iterate over the letters in the string and turn it to upper or lower based on the bit in the permutation.
def letter_case_permutation(S): res =  idx_map = [idx for idx, ch in enumerate(S) if ch.isalpha()] bound = 1 << len(idx_map) temp = list(S).copy() for permutation in range(bound): mask = bound >> 1 for char_idx in idx_map: temp[char_idx] = temp[char_idx].upper() if mask & permutation else temp[char_idx].lower() mask >>= 1 res.append(''.join(temp)) return res
393. UTF-8 Validation
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
For 1-byte character, the first bit is a 0, followed by its unicode code. For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10. This is how the UTF-8 encoding would work:
|Char. number range||UTF-8 octet sequence|
|0000 0000-0000 007F||0xxxxxxx|
|0000 0080-0000 07FF||110xxxxx 10xxxxxx|
|0000 0800-0000 FFFF||1110xxxx 10xxxxxx 10xxxxxx|
|0001 0000-0010 FFFF||11110xxx 10xxxxxx 10xxxxxx 10xxxxxx|
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.
- Reading comprehension problem…
def valid_utf8(data): k = 0 while k < len(data): if (data[k] >> 7 == 0b0): k += 1 else: if (data[k] >> 5 == 0b110): offset = 2 elif (data[k] >> 4 == 0b1110): offset = 3 elif (data[k] >> 3 == 0b11110): offset = 4 else: return False for i in range(1, offset): if (k + i >= len(data) or data[k + i] >> 6 != 0b10): return False k += offset return True