Binary

Question 1

Sum of Two Integers

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

Answer 1

public int getSum(int a, int b) {
        int xor = a ^ b;
        int carry = a & b;
        if (carry == 0) {
            return xor;
        } else {
            return getSum(xor, carry << 1);
        }
    }

https://www.youtube.com/watch?v=kIXhc8nZKIo

Question 2

Number of 1 bits:

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

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It 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 3, the input represents the signed integer. -3.

Answer 2

// you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count = count + (n & 1);
            n = n >>> 1;
        }
        return count;
    }

Question 3

Return all subarrays of 1’s of number:

Given an integer num, return an array of the number of 1’s in the binary representation of every number in the range [0, num].

Answer 3

class Solution {
    public int[] countBits(int num) {
        int[] output = new int[num+1];
        for (int i = 0; i <= num; ++i) {
            output[i] = output[i >> 1] + (i & 1);
        }
        return output;
    }
}

or:

 public int[] countBits(int num) {
        int[] output = new int[num+1];
        for (int i = 0; i <= num; ++i) {
            output[i] = output[i/2] + (i%2);
        }
        return output;
    }

If you have an even number you can right shift and you will get the same number of bits, with odd you lose the LSB, so you add one if its odd.

You can calculate the current set bit by using the previous count at n/2. If its even you don’t have to add a one to if you divide by 2, you will have to add one if its odd, therefore (i & 1)

The top solution uses bit shifting, the bottom uses the actual operators in java

Question 4

Missing Number

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.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Answer 4

public int missingNumber(int[] nums) {
int arraySum = IntStream.of(nums).sum();
int correctSum = (nums.length*(nums.length+1))/2;
return correctSum - arraySum;
}

Pretty obvious w/ closed form solution

Question 5

190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Answer 5

We first intitialize result to 0. We then iterate from
0 to 31 (an integer has 32 bits). In each iteration:
We first shift result to the left by 1 bit.
Then, if the last digit of input n is 1, we add 1 to result. To
find the last digit of n, we just do: (n & 1)
Example, if n=5 (101), n&1 = 101 & 001 = 001 = 1;
however, if n = 2 (10), n&1 = 10 & 01 = 00 = 0).

Finally, we update n by shifting it to the right by 1 (n&raquo_space;= 1). This is because the last digit is already taken care of, so we need to drop it by shifting n to the right by 1.

At the end of the iteration, we return result.

  public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; ++i) { //32 bits
            result <<= 1;
            if (n % 2 != 0) {
                result++;
            }
            n >>= 1;
        }
        return result;
    }