Problem

Given three 32-bit integers x, y, and b, return x if b is 1 and y if b is 0, using only mathematical or bit operations. You can assume b can only be 1 or 0.

Solution

Method 1 - Using bitwise masks

The core idea is to leverage bitwise operations to create masks based on the value of b, which will then be used to select either x or y.

Here’s the approach in a succinct form:

  1. If b is 1, we want to return x.
  2. If b is 0, we want to return y.

We can use bitwise operations to achieve this:

  • Let’s create a mask based on the value of b.
  • If b = 1, the mask will be all 1s.
  • If b = 0, the mask will be all 0s.

Mathematical Bitwise Solution

  1. Compute mask = -b:

    • If b = 1, mask will be all 1s (which is 0xFFFFFFFF for 32-bit integers).
    • If b = 0, mask will be all 0s (which is 0x00000000 for 32-bit integers).

  2. Use the mask to select x or y:

    • result = (x & mask) | (y & ~mask)

Explanation

  • When b is 1, mask becomes 0xFFFFFFFF, so x & mask yields x, and y & ~mask yields 0. The bitwise OR of these results is x.
  • When b is 0, mask becomes 0x00000000, so x & mask yields 0, and y & ~mask yields y. The bitwise OR of these results is y.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution {
    public static int select(int x, int y, int b) {
        // Compute masks based on the value of b
        int mask = -b; // This will be all 1's if b is 1 and all 0's if b is 0
        return (x & mask) | (y & ~mask);
    }

    public static void main(String[] args) {
        int x = 42;
        int y = 7;
        int b1 = 1;
        int b2 = 0;

        System.out.println(select(x, y, b1)); // Output: 42
        System.out.println(select(x, y, b2)); // Output: 7
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def select(x, y, b):
    # Compute the mask based on the value of b
    mask = -b  # This will be all 1's if b is 1 and all 0's if b is 0
    return (x & mask) | (y & ~mask)


# Example usage:
x = 42
y = 7
b1 = 1
b2 = 0

print(select(x, y, b1))  # Output: 42
print(select(x, y, b2))  # Output: 7

Complexity

  • ⏰ Time complexity: O(1)
    • This is because all operations (computing the mask, bitwise AND, bitwise NOT, bitwise OR) are constant-time operations.
  • 🧺 Space complexity: O(1)