Set Clear Toggle a Specific Bit in DSA Java - Time & Space Complexity

Time Complexity: Set Clear Toggle a Specific Bit

O(1)

Understanding Time Complexity

We want to understand how long it takes to change a specific bit in a number.

How does the time needed grow when we work with bigger numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public class BitOperations {
    public static int setBit(int num, int pos) {
        return num | (1 << pos);
    }

    public static int clearBit(int num, int pos) {
        return num & ~(1 << pos);
    }

    public static int toggleBit(int num, int pos) {
        return num ^ (1 << pos);
    }
}
    

This code sets, clears, or toggles a bit at a given position in an integer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise shift and bitwise logical operations.
• How many times: Each operation runs once per method call, no loops or recursion.

How Execution Grows With Input

The time to set, clear, or toggle a bit does not increase with the size of the number.

Input Size (n)	Approx. Operations
10 (bits)	1 operation
100 (bits)	1 operation
1000 (bits)	1 operation

Pattern observation: The operation count stays the same no matter how big the number is.

Final Time Complexity

Time Complexity: O(1)

This means the time to set, clear, or toggle a bit is constant and does not depend on input size.

Common Mistake

[X] Wrong: "Changing a bit takes longer for bigger numbers because they have more bits."

[OK] Correct: Bitwise operations work directly on fixed-size integers, so changing one bit is always a single step.

Interview Connect

Knowing that bit operations run in constant time helps you explain efficient low-level data manipulation clearly and confidently.

Self-Check

"What if we tried to set or clear bits in a very large number represented as an array of bits? How would the time complexity change?"

Practice

1. What does the operation num | (1 << k) do to the integer num in terms of its bits?

easy

A. Toggles the k-th bit of num

B. Clears the k-th bit of num to 0

C. Sets the k-th bit of num to 1

D. Checks if the k-th bit of num is set

Solution

1. Step 1: Understand the bit shift operation

   1 << k creates a number with only the k-th bit set to 1 and all others 0.

2. Step 2: Apply bitwise OR with num

   Using num | (1 << k) sets the k-th bit of num to 1 without changing other bits.

3. Final Answer:

   Sets the k-th bit of num to 1 -> Option C

4. Quick Check:

   Set bit = OR with 1 shifted [OK]

Hint: Use OR with 1 shifted to set a bit [OK]

Common Mistakes:

• Confusing OR with AND operation
• Thinking it clears or toggles the bit
• Misunderstanding bit positions starting at 0

2. Which of the following Java statements correctly clears (sets to 0) the 3rd bit (0-based) of an integer variable num?

easy

A. num = num & (1 << 3);

B. num = num & ~(1 << 3);

C. num = num ^ (1 << 3);

D. num = num | (1 << 3);

Solution

1. Step 1: Understand clearing a bit

   To clear a bit, we AND with a mask that has 0 at that bit and 1s elsewhere.

2. Step 2: Create mask and apply

   ~(1 << 3) creates a mask with all 1s except 0 at bit 3. ANDing num with this clears bit 3.

3. Final Answer:

   num = num & ~(1 << 3); -> Option B

4. Quick Check:

   Clear bit = AND with NOT mask [OK]

Hint: Clear bit by AND with NOT of shifted 1 [OK]

Common Mistakes:

• Using OR instead of AND to clear bits
• Using XOR which toggles bits
• Using AND with shifted 1 which keeps only that bit

3. What is the output of the following Java code?

int num = 10; // binary 1010
int k = 1;
num = num ^ (1 << k);
System.out.println(num);

medium

A. 10

B. 14

C. 12

D. 8

Solution

1. Step 1: Understand initial value and bit positions

   num = 10 in binary is 1010. Bit positions (0-based) from right: bit0=0, bit1=1, bit2=0, bit3=1.

2. Step 2: Apply XOR to toggle bit 1

   1 << 1 is 0010. XOR toggles bit 1: 1010 ^ 0010 = 1000 (binary) which is 8 decimal.

3. Final Answer:

   8 -> Option D

4. Quick Check:

   XOR toggles bit 1: 10 -> 8 [OK]

Hint: XOR toggles the bit at position k [OK]

Common Mistakes:

• Confusing XOR with OR or AND
• Misreading bit positions starting at 1 instead of 0
• Incorrect binary to decimal conversion

4. The following Java code is intended to toggle the 2nd bit of num. What is the error?

int num = 5; // binary 0101
int k = 2;
num = num & (1 << k);
System.out.println(num);

medium

A. It clears all bits except the 2nd bit instead of toggling

B. It toggles the wrong bit

C. It causes a syntax error

D. It sets the 2nd bit to 1 always

Solution

1. Step 1: Analyze the operation used

   The code uses AND with 1 << k, which keeps only the k-th bit and clears others.

2. Step 2: Understand toggle operation

   Toggle requires XOR, not AND. AND here does not toggle but masks all bits except bit 2.

3. Final Answer:

   It clears all bits except the 2nd bit instead of toggling -> Option A

4. Quick Check:

   Toggle = XOR, not AND mask [OK]

Hint: Toggle bits using XOR, not AND [OK]

Common Mistakes:

• Using AND instead of XOR to toggle bits
• Confusing bit positions
• Expecting output without understanding bitwise operations

5. Given an integer num, write a Java expression to toggle the 0th bit only if it is currently set (1), otherwise leave num unchanged. Which expression achieves this?

hard

A. num = (num & (1 << 0)) != 0 ? num ^ (1 << 0) : num;

B. num = num & ~(1 << 0);

C. num = num ^ (1 << 0);

D. num = num | (1 << 0);

Solution

1. Step 1: Check if 0th bit is set

   Use (num & (1 << 0)) != 0 to test if bit 0 is 1.

2. Step 2: Toggle bit 0 only if set

   If bit 0 is set, toggle it with XOR; else keep num unchanged.

3. Final Answer:

   num = (num & (1 << 0)) != 0 ? num ^ (1 << 0) : num; -> Option A

4. Quick Check:

   Conditional toggle only if bit set [OK]

Hint: Use conditional check before toggling bit [OK]

Common Mistakes:

• Toggling bit unconditionally
• Using OR which always sets bit
• Clearing bit without condition