Bit manipulation

Question 1

Binary Gap

Given a positive integer n, find and return the longest distance between any two adjacent 1’s in the binary representation of n. If there are no two adjacent 1’s, return 0.

Two 1’s are adjacent if there are only 0’s separating them (possibly no 0’s). The distance between two 1’s is the absolute difference between their bit positions. For example, the two 1’s in “1001” have a distance of 3.

Answer 1

int is 32 bits, so use an array of length 32 to store 0’s and 1’s in the binary representation:
int[] binary = new int[32];

Fill in the array: right shift by index number and then check if that bit is a 1

    int[] binary = new int[32];
    int lastOneIndex = -1; 
    int result=0;
    for(int index=0; index < 32; index++) {
        if (((n >> index) & 1) != 0) {
            if (lastOneIndex >= 0)
                result = Math.max(result, index - lastOneIndex);
            lastOneIndex = index;
        }
    }
    return result;

Question 2

Count Pairs of Points With Distance k

You are given a 2D integer array coordinates and an integer k, where coordinates[i] = [xi, yi] are the coordinates of the ith point in a 2D plane.

We define the distance between two points (x1, y1) and (x2, y2) as (x1 XOR x2) + (y1 XOR y2) where XOR is the bitwise XOR operation.

Return the number of pairs (i, j) such that i < j and the distance between points i and j is equal to k.

Input: coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
Output: 10
Explanation: Any two chosen pairs will have a distance of 0. There are 10 ways to choose two pairs.

Answer 2

XOR is it’s own inverse. If a XOR b = c, then a XOR c = b and b XOR c = a

Distance between (x1, y1) and (x2, y2) would be: x1 XOR x2 + y1 XOR y2
Checking all possible pairs would be O(N^2)

Decompose k as k = a+b where a = x1 XOR x2 and b = y1 XOR y2
So if a = x1 XOR x2, then x1 = a XOR x2, use this along with a hashmap to identify such pairs in O(N) time.

    Map<List<Integer>, Integer> frequency = new HashMap<>();
    int result = 0;
    for(List<Integer> coordinate: coordinates) {
        int x = coordinate.get(0);
        int y = coordinate.get(1);
        for(int xorValue = 0; xorValue <= k; xorValue++) {
            int yorValue = k - xorValue;
            int targetX = x ^ xorValue;
            int targetY = y ^ yorValue;
            List<Integer> targetPair = List.of(targetX, targetY);
            result += frequency.getOrDefault(targetPair, 0);
        }
        frequency.put(coordinate, frequency.getOrDefault(coordinate, 0)+1);
    }
    return result;