Bitwise operations can often feel like magic, but they follow very strict logical patterns once you peek under the hood. In this guide, we will break down a problem that asks us to reverse-engineer a bitwise OR operation to find the smallest possible starting value.

---

Problem Summary

You’re given: An array nums consisting of prime integers.

Your goal: For each number in nums, find the smallest non-negative integer ans[i] such that . If no such integer exists, set the value to -1.

---

Intuition

To solve this, we need to understand what happens when we perform .

When you add 1 to a binary number, the rightmost block of continuous 1s "flips" to 0s, and the first 0 to their left becomes a 1. For example, if is (binary 11), then is (binary 12).

The operation effectively fills in the first 0 bit to the left of the trailing 1s. This means must be the result of taking some number and turning one of its 0 bits into a 1. Specifically, if has a trailing block of 1s, like , the smallest that satisfies the condition is found by changing the highest bit of that last group of 1s into a 0.

Wait, what about the number 2? The number 2 in binary is . There is no integer where . If , . If , . Therefore, for the prime number 2, the answer is always -1.

---

Walkthrough: Understanding the Examples

Let’s look at Example 1 with nums = [2, 3, 5, 7].

1. For 2 (): As discussed, no works. Result: -1.
2. For 3 (): The trailing ones are in the 1s and 2s place. The "leading one" of this group is (). . Check: . Result: 1.
3. For 5 (): The trailing group of ones is just the last bit (). . Check: . Result: 4.
4. For 7 (): The trailing ones are . The leading one of this group is . . Check: . Result: 3.

---

Code Blocks

C++

class Solution {
public:
vector<int> minBitwiseArray(vector<int>& nums) {
vector<int> ans;

for (const int num : nums) {
// If the number is 2, no solution exists based on the OR property.
if (num == 2) {
ans.push_back(-1);
} else {
ans.push_back(num - getLeadingOneOfLastGroupOfOnes(num));
}
}

return ans;
}

private:
// Finds the highest power of 2 that is part of the trailing block of 1s.
int getLeadingOneOfLastGroupOfOnes(int num) {
int leadingOne = 1;
// Keep shifting left as long as we encounter 1s from the right.
while ((num & leadingOne) > 0) {
leadingOne <<= 1;
}
// Shift back once to get the position of the highest 1 in that group.
return leadingOne >> 1;
}
};

Python

class Solution:
def minBitwiseArray(self, nums: list[int]) -> list[int]:
ans = []

for num in nums:
if num == 2:
ans.append(-1)
else:
# Find the leading one of the last group of 1s
leading_one = 1
while (num & leading_one) > 0:
leading_one <<= 1

# Subtract the highest bit of the trailing ones
ans.append(num - (leading_one >> 1))

return ans

JavaScript

/**
* @param {number[]} nums
* @return {number[]}
*/
var minBitwiseArray = function(nums) {
return nums.map(num => {
if (num === 2) return -1;

let leadingOne = 1;
// Identify the trailing block of continuous set bits (1s)
while ((num & leadingOne) > 0) {
leadingOne <<= 1;
}

// Return num minus the most significant bit of that trailing block
return num - (leadingOne >> 1);
});
};

---

Key Takeaways

• Bitwise OR Property: The operation essentially targets the lowest-significant 0 bit and flips it to 1.
• Bit Manipulation Patterns: Using while ((num & leadingOne) > 0) is a common pattern to traverse the bits of a number from right to left.
• Edge Case Handling: Recognizing that certain numbers (like 2) cannot be formed by specific bitwise patterns is crucial for correctness.

---

Final Thoughts

This problem is a fantastic exercise in "bit-thinking." In real-world software engineering, bitwise logic is the backbone of embedded systems, high-performance flags in game engines, and network protocols where saving every bit of space matters. Understanding how interacts with is also a classic trick used in Fenwick Trees (Binary Indexed Trees) and other advanced data structures. Mastering these small patterns makes you much faster at identifying optimizations in low-level systems.