Bit Manipulation Questions Part 3
20. Reverse bits
Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
Bit manipulation
def reverse_bits(n):
m = 0
i = 0
while i < 32:
m = (m << 1) + (n & 1)
n >>= 1
i += 1
return m
# or while n: then remove i+=1
def reverse_bits2(n):
m = 0
while n:
m = (m << 1) + (n & 1)
n >>= 1
return m
print(reverse_bits2(678))
def reverseBits(n):
res = 0
for i in range(32):
res <<= 1
res |= ((n >> i) & 1)
return res
String manipulation. The fuss of padding a given number with 0s. If we want bin(3) in python, it returns “11” and not “000…11”. Then if we reverse it i.e., reverse of “11” is “11” but expected answer is “110000… “(reverse of 000…11).
class Solution:
def reverseBits(n):
s = bin(n)[2:]
s = "0"*(32 - len(s)) + s #to pad with 0s
t = s[::-1]
return int(t,2) #to return in binary format
Another string manipulation. Pad with spaces, replace spaces with 0.
class Solution:
def reverseBits(n):
n = bin(n)[2:]
n = '%32s' % n
n = n.replace(' ','0')
return int(n[::-1],2)
# using [:1:-1] instead of [:2] and [::-1]
def reverseBits(n):
"""
:type n: int
:rtype: int
"""
b = bin(n)[:1:-1]
return int(b + '0'*(32-len(b)), 2)
21. Single number
Given an array of integers, every element appears twice except for one. Find that single one.
(Note, This also works for finding a number occurring odd number of times, where all the other numbers appear even number of times. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?)
BIT XOR (Without using extra memory.)
def find_single(a):
ans = 0
for n in a:
ans ^= n
return ans
Note. It relies on the fact that the duplicate numbers appear exactly twice (or other even number), not three times e.g.
Python stdlib
import collections
def singleNumber(nums):
num_count = collections.Counter(nums)
return [x for x in num_count if num_count[x] == 1]
Reminder of how collections.Counter(L) works: >>> import collections >>> L = [2,4,5,2] >>> collections.Counter(L) Counter({2: 2, 4: 1, 5: 1})
using set()
def singleNumber(nums):
return 2 * sum(set(nums)) - sum(nums)
loop, extra array (remove, append)
def singleNumber(nums):
no_repeat_array=[]
for index, item in enumerate(nums):
if item in no_repeat_array:
no_repeat_array.remove(item)
else:
no_repeat_array.append(item)
return no_repeat_array.pop()
22. Single number2
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
(Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?)
Solution
def singleNumber(self, nums):
# for [a,a,b,a] array
# 3*(a+b) - (a+a+b+a) = 2b
return int((3*(sum(set(nums))) - sum(nums))//2) #generator doesn't use space
# The same, but more elaboration
def f2(a):
s_set = sum(set(a)) * 3
s_a = sum(a)
res = (s_set - s_a) / 2
return res
# Python stdlib (but uses memory)
import collections
def singleNumber(nums):
num_count = collections.Counter(nums)
return [x for x in num_count if num_count[x] == 1]
23. Single number3
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.
# Stdlib
import collections
def singleNumber(nums):
num_count = collections.Counter(nums)
return [x for x in num_count if num_count[x] == 1]
24. (LC 401) Binary Watch
Note. The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”. The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.
Hint: each of the numbers on the watch (1,2,4,8,16,32) has one bit 1 in binary:
>>> bin(8); bin(16)
'0b1000'
'0b10000'
# IDEA : GREEDY
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
ans = []
for h in range(12):
for m in range(60):
if (bin(h)+ bin(m)).count('1') == num:
ans.append('%d:%02d' % (h, m))
return ans
# The same but using list comprehension
def readBinaryWatch(num):
return ['%d:%02d' % (h, m)
for h in range(12) for m in range(60)
if (bin(h) + bin(m)).count('1') == num]
# format
>>> m=4
>>> '%02d' % m
'04'
>>> bin(2) + bin(12)
'0b100b1100' # 3 1s
25. Bitwise AND of-numbers-range
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
# Solution 1
def f8(m, n):
while n > m:
n &= n-1
return n
m, n = 5, 7
print(f8(m,n))
>>> 7&6&5
4
# Note, the following won’t work. It will be an infinite loop. You have to be changing n, the bigger number. & diminishes n. Changing m, makes m smaller, it will never be greater than n, i.e. infinite loop. Going 5,6,7. m=5&6=4, m=4&7=4, m=4&8=0 etc.
def f9(m, n):
while n > m:
m &= m+1
return m
# Solution my v
def f(a):
ans = a[0]
for i in range(a[0] + 1, a[1] + 1):
ans = ans ^ i
return ans
a = [5, 7]
print(f(a)) #4
26. (LC 461) Hamming distance
(Easy) The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, return the Hamming distance between them.
# Solution 1 (Bitwise operator)
def hammingDistance(x, y):
return bin(x ^ y).count('1')
It uses the properties of Xor operator. Recall, that xor evaluates to 1 if the two compared numbers are 0 and 1 (1^1, 0^0 evaluate to 0)
So the resulting number evaluates to 1 only if the two compared numbers are different. Then we simply count 1s with .count(‘1’)
### My solutions
# 1
def f31(x, y):
z = x ^ y
return bin(z).count('1')
print(f31(1, 4)) #2
print(f31(29, 5)) #2
# 2
def f32(x, y):
z = x ^ y
count = 0
while z:
if z & 1:
count += 1
z >>= 1
return count
print(f32(1, 4)) #2
print(f32(29, 5)) #2
27. (LC 477) Total Hamming Distance
(Medium) The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.
Example 1: Input: nums = [4,14,2] Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). The answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Example 2: Input: nums = [4,14,4] Output: 4
### Solution
def hammingDistance(x, y):
return bin(x ^ y).count('1')
def total_hd(nums):
ans = 0
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
dis = hammingDistance(nums[i], nums[j])
ans += dis
return ans
nums = [4,14,2]
print(total_hd(nums)) #6
# My solution 2
# (Use library to make pairs and built in method to count 1s.)
import itertools
def total_ham_dist3(a):
td = 0 # total distance
pairs = list(itertools.combinations(a, 2))
for pair in pairs:
n1 = pair[0]
n2 = pair[1]
td += (n1 ^ n2).bit_count()
return td
nums = [4, 14, 2]
print(total_ham_dist3(nums))
# My solution 1
# (Uses XOR and & to count hamming distance. But as for putting whatever way of
# counting into a separate function - yes it is better.)
def f34(a):
ham_sum = 0
for i in range(len(a)-1):
for j in range(i+1, len(a)):
ham = 0
ij = a[i]^a[j]
while ij:
ij = ij & (ij - 1)
ham += 1
ham_sum += ham
return ham_sum
a = [4,14,2]
a2 = [4,14,4]
print(f34(a)) #6
print(f34(a2)) #4
28. Maximum-product-of-word-lengths
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
### Solution
# Using set() and itertools std lib
import itertools
def common(a, b):
return set(a) & set(b)
def product_score(w1, w2):
return 0 if common(w1, w2) else len(w1) * len(w2)
def maxProduct(words):
return max(product_score(w1, w2)
for (w1, w2) in itertools.combinations(words, 2))
itertools.combinations(iterable, r)>>> list(itertools.combinations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
>>> list(itertools.combinations([1,2,3, 4], 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
### Remake
def f(w1, w2):
"""no common letters"""
if len(set(w1) & set(w2)) == 0:
return True
return False
def max_prod(a):
return max(len(i) * len(j) for (i, j) in itertools.combinations(a, 2) if f(i, j))
### No magic at all
def unique(w1, w2):
if len(set(w1) & set(w2)) == 0:
return True
return False
def max_len(a):
combos = itertools.combinations(a, 2)
lens = []
for x, y in combos:
if unique(x, y):
l = len(x) * len(y)
lens.append(l)
return max(lens)
a = ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
print(max_len(a)) #16
29. (LC 421) Maximum XOR of Two Numbers in an Array
# Solution
def findMaximumXOR(nums):
ans = mask = 0
for i in range(32)[::-1]:
mask += 1 << i #alternatively mask |= 1<<i
prefixSet = {n & mask for n in nums}
temp = ans | 1 << i
for prefix in prefixSet:
if temp ^ prefix in prefixSet:
ans = temp
break
return ans
nums = [3,10,5,25,2,8]
print(findMaximumXOR(nums)) #28 (25^5)
Explained.
-We are basing our solution on the fact that the max xor is 1111.. Now, how many 1s to take, we could take the len of max number, or just some max possible, i.e. 32.
for i in range(32)[::-1]:mask += 1 << iprefixSet = {n & mask for n in nums}temp = ans | 1 << i(Why, because before that tepm = 100000.., is a large number, we are not going to find temp ^ prefix in prefixes, so we loop fruitlessly until we start finding for shorter numbers, smaller i-s, like i= 4, for num 25 (10000) first MSB revealed).