Bit Manipulation

Question 1

Write a function that takes the binary representation of an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Answer 1

• n % 2 to get the one’s place
• shift the bit by 1 every time (n = n&raquo_space; 1)

def hammingWeight(self, n: int) -> int:
count = 0
while n:
count += n % 2 # gives you the one’s place
n = n&raquo_space; 1 # bit shifted, much faster than dividing
return count

O(1) / O(1) (because every binary number is 32 bits, the while loop runs 32 times)

Question 2

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

Answer 2

• Write out the first 8 binary numbers and see the pattern….it’s a dynamic programming problem.
• The formula is 1 + dp[i - offset]
• The offset is the power of 2 that you need to subtract to get within range of the previous power of two. This updates every time you get a new significant digit (when offset * 2 == i)

def countBits(self, n: int) -> List[int]:
res = [0]
offset = 1
for i in range(1, n + 1):
if offset * 2 == i:
offset *= 2
res.append(1 + res[i - offset])

    return res

O(n) / O(n)

Question 3

Reverse bits of a given 32 bits unsigned integer.

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Answer 3

• going through n from the first digit to the last, and multiplying it by the powers of 2 starting at 2^31def reverseBits(self, n: int) -> int:
  res = 0
  for i in range(31, -1, -1):
  if n % 2 == 1:
  res += pow(2, i)
  n&raquo_space;= 1
  return res

Question 4

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Answer 4

• xor all numbers in the range with all numbers from input array.
• Xor cancels out all the numbers that are the same, leaving you with the one that’s missing.

ALTERNATIVELY
Sum all numbers in range and subtract the sum of input array from that.

Question 5

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Answer 5

• The Xor operator will add two numbers, but won’t handle carrying over the 1.
• & of the two numbers carries the 1.
• Then you need to add the ^ result and & result.
• Repeat this process until & result (b) == 0
• This only works in Java…python requires masking and things.

O(1)