Continuing through the Blind 75 summarizations, here are the binary-related questions. There are not many tricks with these questions, this is just testing knowledge on binary operations. Previous post on array algorithms

Sum of Two Integers

Find sum of two integers without using built in integer operators.

Solution with O(1)/O(1):

Use binary operators:

1. Take binary AND of the input integers, shift left 1, that is the carry
2. Take binary XOR of the input integers, that is the result
3. Recursively repeat with result and carry instead of the input integers, until the carry is 0

Number of 1 Bits

Given an integer, return the number of 1 bits in its binary representation.

Solution with O(1)/O(1):

For each bit:

1. Use binary AND with 1 to determine if the last bit is a 1 and add that to the result
2. Bit shift to the right

Counting Bits

Generate an array of integers, where each value represents the number of 1 bits in the binary representation of the index. The input integer determines the array length.

Solution with O(N)/O(1):

For each value in the array, the number can be calculated recursively, take:

• The last digit of the binary representation of the index, plus
• The number of 1 bits in the number divided by 2 (i.e. find the result already calculated at the index bit shifted 1 to the right)

This works because binary numbers repeat when multiplied by 2, think about what happens when you multiply a base-10 number by 10.

Missing Number

Given an array of numbers from 0 to the length of the array, find the missing number.

Solution with O(N)/O(1):

Iterate through, XOR all numbers with all indexes, the missing number will be left.

Reverse Bits

Reverse the bits of a 32 bit unsigned integer.

Solution with O(1)/O(1):

For each bit of the number:

1. Add the rightmost bit from the input to the result
2. Shift the result left
3. Shift the input right

Next Post on Graph Algorithms