Bitwise AND of Numbers Range

▶

Steps

setup

Initialize variables

We start with left = 5 and right = 7. Both numbers are converted to 32-bit binary for visualization.

💡 Initialization shows the starting point of the algorithm and the binary forms of the inputs.

Line:

left = 5
right = 7

💡 Understanding the binary representation of inputs is crucial to see how bitwise operations affect them.

compare

Check if right > left

We compare right (7) and left (5). Since 7 > 5, we proceed to clear the rightmost set bit of right.

💡 This comparison controls the loop; the algorithm continues modifying right while it is greater than left.

Line:

while right > left:

💡 The loop condition ensures we only clear bits in right until it is no longer greater than left.

shrink

Clear rightmost set bit of right

We clear the rightmost set bit of right by computing right = right & (right - 1). For right=7, right-1=6, so right becomes 7 & 6 = 6.

💡 Clearing the rightmost set bit reduces right, moving it closer to left and revealing common bits.

Line:

right = right & (right - 1)

💡 This operation removes the least significant '1' bit from right, a key step in the algorithm.

compare

Check if right > left again

Now right is 6, left is still 5. Since 6 > 5, we continue the loop to clear another rightmost set bit.

💡 Each loop iteration checks if right is still greater than left to decide whether to continue clearing bits.

Line:

while right > left:

💡 The loop condition is still true, so right will be modified again.

shrink

Clear rightmost set bit of right again

We clear the rightmost set bit of right again: right = 6 & (6 - 1) = 6 & 5 = 4.

💡 Clearing the rightmost set bit again moves right closer to left and reveals the common prefix bits.

Line:

right = right & (right - 1)

💡 This step removes the least significant '1' bit from right again, changing it from 6 to 4.

compare

Check if right > left again

Now right is 4 and left is 5. Since 4 is not greater than 5, the loop ends.

💡 The loop condition fails, so we stop clearing bits and prepare to return the result.

Line:

while right > left:

💡 The algorithm has found the common prefix bits shared by all numbers in the range.

reconstruct

Return final result

The algorithm returns right = 4 as the bitwise AND of all numbers from 5 to 7.

💡 Returning right now gives the correct AND result without checking each number individually.

Line:

return right

💡 The final right value represents the common bits shared by all numbers in the range.

compare

Loop condition check after first clear

After clearing the rightmost set bit once, we check if right (6) is still greater than left (5).

💡 This step explicitly shows the loop condition re-evaluation after the first bit clear.

Line:

while right > left:

💡 The loop continues because right remains greater than left after one bit clear.

compare

Loop condition check after second clear

After clearing the rightmost set bit a second time, we check if right (4) is still greater than left (5).

💡 This step explicitly shows the loop condition re-evaluation after the second bit clear.

Line:

while right > left:

💡 The loop ends because right is no longer greater than left after the second bit clear.

reconstruct

Final result visualization

We visualize the final bitwise AND result of the range, which is right = 4.

💡 This step confirms the final answer in both binary and decimal forms.

Line:

return right

💡 The final right value represents the common bits shared by all numbers in the range.

def rangeBitwiseAnd(left: int, right: int) -> int:
    # STEP 1: Initialize left and right
    while right > left:  # STEP 2,4,6,8,9: Loop condition check
        # STEP 3,5: Clear rightmost set bit of right
        right = right & (right - 1)
    # STEP 7,10: Return final result
    return right

if __name__ == '__main__':
    print(rangeBitwiseAnd(5, 7))  # Output: 4

📊

Bitwise AND of Numbers Range - Watch the Algorithm Execute, Step by Step

Watching each bit manipulation step helps you understand how the algorithm efficiently finds the bitwise AND of a range without checking every number.

Initialization

A

0

1

0

1

=5

B

0

1

1

1

=7

Check if right > left

A

0

1

0

1

=5

B

0

1

1

1

=7

💡 Loop continues because right is greater than left

Clear rightmost set bit of right

A

0

1

0

1

=5

B

0

1

1

0

=6

💡 Rightmost set bit cleared: 7 (0111) -> 6 (0110)

Check if right > left

A

0

1

0

1

=5

B

0

1

1

0

=6

💡 Loop continues because right is still greater than left

Clear rightmost set bit of right

A

0

1

0

1

=5

B

0

1

0

0

=4

💡 Rightmost set bit cleared: 6 (0110) -> 4 (0100)

Check if right > left

A

0

1

0

1

=5

B

0

1

0

0

=4

💡 Loop ends because right is no longer greater than left

Return final AND result

A

0

1

0

1

=5

B

0

1

0

0

=4

────────

=

0

1

0

0

=4

💡 Final AND result is 4 (0100)

Check if right > left

A

0

1

0

1

=5

B

0

1

1

0

=6

💡 Loop continues because right is still greater than left

Check if right > left

A

0

1

0

1

=5

B

0

1

0

0

=4

💡 Loop ends because right is no longer greater than left

Return final AND result

A

0

1

0

1

=5

B

0

1

0

0

=4

────────

=

0

1

0

0

=4

💡 Final AND result is 4 (0100)

Key Takeaways

✓ Clearing the rightmost set bit of 'right' repeatedly finds the common prefix bits shared by all numbers in the range.

This insight is hard to see from code alone because the bitwise operation's effect on the range is not obvious without visualization.

✓ The loop condition 'right > left' controls when to stop clearing bits, ensuring the final 'right' is the AND of the entire range.

Understanding this control flow is easier when you see the values change step-by-step.

✓ The final returned value is the bitwise AND of all numbers in the range without checking each number individually.

This shows the efficiency of the algorithm and why it is optimal compared to naive approaches.

Practice

1. You are given an array of integers and need to find two numbers whose XOR is the maximum possible. Which approach guarantees an optimal solution for this problem?

easy

A. Build a binary trie of all numbers and traverse it to find the maximum XOR pair.

B. Use a dynamic programming approach to build XOR values incrementally.

C. Use a greedy approach by iteratively guessing the maximum XOR bit from the most significant bit down.

D. Use brute force nested loops to check XOR of every pair and track the maximum.

Solution

1. Step 1: Understand problem constraints

   We want to find two numbers maximizing XOR, which requires bitwise comparisons across all numbers.

2. Step 2: Evaluate approaches

   Brute force works but is O(n²), greedy bit-by-bit can fail on some inputs due to incomplete prefix checks, while trie-based stores bits for all numbers and efficiently finds complementary bits to maximize XOR.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie-based approach is optimal and guaranteed to find max XOR [OK]

Hint: Trie stores bits for efficient max XOR search [OK]

Common Mistakes:

• Believing greedy bit-by-bit always works
• Thinking DP applies here
• Assuming brute force is optimal

2. You need to determine if a given positive integer can be expressed as 4 raised to some integer power (i.e., n = 4^k for k ≥ 0). Which approach guarantees an optimal O(1) time solution without loops or recursion?

easy

A. Use logarithms to check if log base 4 of the number is an integer.

B. Iteratively divide the number by 4 until it becomes 1 or a non-divisible remainder is found.

C. Check if the number is a power of two and then verify if the set bit is in an even position using bitmasking.

D. Use dynamic programming to build up powers of four and compare with the number.

Solution

1. Step 1: Understand the problem requirement

   The problem asks for a constant-time check to determine if a number is a power of four, which means no loops or recursion.

2. Step 2: Evaluate approaches for O(1) time

   Using bitmasking to check if the number is a power of two and if the single set bit is in an even position is a known O(1) approach. Logarithm checks involve floating point operations and can have precision issues, so they are not guaranteed to be optimal or reliable in constant time. Iterative division and dynamic programming are not O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmasking approach uses constant time bit operations [OK]

Hint: Bitmasking checks power of two and bit position in O(1)

Common Mistakes:

• Confusing power of two check with power of four
• Using loops despite O(1) requirement
• Relying on floating point logarithm checks which can be imprecise

3. Given the following Python code, what is the output of isPowerOfFour(16)?

easy

A. True

B. False

C. Raises an error due to floating point precision

D. None

Solution

1. Step 1: Calculate log2(16)

   log2(16) = 4, dividing by 2 gives 2.0.

2. Step 2: Check if 2.0 equals int(2.0)

   2.0 == 2 is True, so the function returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   16 is 4^2, so output True is expected [OK]

Hint: log2(16)/2 = 2.0 equals int(2) -> True

Common Mistakes:

• Assuming floating point error causes failure
• Confusing power of two with power of four

4. Consider the following buggy Python code intended to generate Gray code sequence. Which line contains the subtle bug that breaks the Gray code property?

medium

A. Line 2: Using XOR with (i << 1) instead of (i >> 1)

B. Line 3: Incorrect range boundary in range(1 << n)

C. Line 1: Missing base case for n=0

D. Line 5: Printing the result instead of returning

Solution

1. Step 1: Identify the bitwise operation used

   The code uses i ^ (i << 1) instead of the correct i ^ (i >> 1).

2. Step 2: Understand impact on Gray code property

   Left shifting i doubles the value, causing incorrect bit patterns and breaking the one-bit difference property between consecutive numbers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct Gray code uses right shift, not left shift [OK]

Hint: XOR with right shift generates Gray code; left shift breaks it [OK]

Common Mistakes:

• Confusing left and right bit shifts in XOR formula
• Ignoring base case n=0 which is trivial but not critical here
• Misunderstanding range boundaries or print vs return

5. Identify the bug in the following trie-based maximum XOR code snippet:

medium

A. Line with 'node = node.children[bit]' does not check if 'bit' exists in children.

B. Line with 'if bit not in node.children:' should check for toggled_bit instead.

C. Line with 'max_xor |= (1 << i)' should be outside the if condition.

D. Line with 'node = self.root' should be inside the for loop.

Solution

1. Step 1: Analyze traversal in findMaxXor

   When toggled_bit is not found, code moves to node.children[bit] without checking if bit exists, risking KeyError.

2. Step 2: Identify missing null check

   Should use node.children.get(bit) or check existence before accessing to avoid runtime error.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing check causes crash on inputs missing bit child [OK]

Hint: Always check child existence before traversal [OK]

Common Mistakes:

• Assuming child always exists
• Confusing toggled_bit check
• Misplacing max_xor update