Definition
- Complement – the number formed by flipping every bit of the input, but only within its bit width (up to and including the highest set bit).
- Mask construction – build an all-ones mask with
(1 << bitCount) - 1, wherebitCountis the number of bits in the input. - XOR flip –
num ^ maskflips exactly the bits under the mask, producing the complement. - Bit counting – find the width by right-shifting a copy until zero, counting shifts.
- Why limit width – flipping all 32 bits would turn leading zeros into ones, giving a huge or negative number.
At the National Bank of India, a legacy device encodes an account flag as a small binary number, and a downstream system needs the inverted mirror flag. Rajesh makes a stamp of all ones the same width as the flag and presses it with XOR to flip exactly those bits, leaving higher bits untouched.
Understanding the Concepts
What is the complement of a base-10 number?
The complement of a number is formed by flipping every bit in its binary representation, but only the bits up to and including the highest set bit. For example, 5 in binary is 101, and flipping gives 010, which is 2. We do not flip the leading zeros of the 32-bit integer representation.
package com.bank.service;
public class BitComplement {
public int findComplement(int num) {
if (num == 0) return 1;
int bitCount = 0;
int temp = num;
while (temp > 0) {
bitCount++;
temp >>= 1;
}
int mask = (1 << bitCount) - 1;
return num ^ mask;
}
}
Why do we limit the flip to the number's bit width?
If we flipped all 32 bits of an int, the leading zeros would become ones, producing a very large or negative number. For example, 5 as a full 32-bit int has 29 leading zeros. Flipping all 32 bits gives 11111111111111111111111111111010, which is -6 in two's complement. The problem asks only for the complement within the used bits.
package com.bank.service;
public class WhyLimitWidth {
public static void main(String[] args) {
int num = 5; // binary: 101
System.out.println("Full 32-bit flip: " + (~num)); // -6
System.out.println("Width-limited flip: " + (num ^ 0b111)); // 2
}
}
Full 32-bit flip: -6
Width-limited flip: 2
How do you find the bit width?
Right-shift a copy of the number until it becomes zero, counting the shifts. This gives the position of the highest set bit plus one, which is the bit width. Java also provides Integer.highestOneBit() and Integer.numberOfLeadingZeros() as alternatives.
package com.bank.service;
public class BitWidthDemo {
public static void main(String[] args) {
int num = 8; // binary: 1000
int bitCount = 0;
int temp = num;
while (temp > 0) {
bitCount++;
temp >>= 1;
}
System.out.println("Bit width of " + num + ": " + bitCount); // 4
// Alternative: 32 - numberOfLeadingZeros
int altWidth = 32 - Integer.numberOfLeadingZeros(num);
System.out.println("Alternative: " + altWidth); // 4
}
}
Bit width of 8: 4
Alternative: 4
How does the mask-and-XOR work?
The mask is a run of ones as wide as the number. XOR with ones flips every bit: 0 XOR 1 = 1, and 1 XOR 1 = 0. So num ^ mask flips exactly the bits the number uses.
package com.bank.service;
public class MaskXORDemo {
public static void main(String[] args) {
int num = 8; // binary: 1000
int mask = (1 << 4) - 1; // binary: 1111 = 15
int complement = num ^ mask;
System.out.println(num + " (" + Integer.toBinaryString(num)
+ ") XOR " + mask + " (" + Integer.toBinaryString(mask)
+ ") = " + complement + " (" + Integer.toBinaryString(complement) + ")");
}
}
8 (1000) XOR 15 (1111) = 7 (111)
What are the edge cases?
The main edge case is zero. Its binary representation has no set bits, so the bit width is zero. By convention, the complement of zero is one. Another edge case is a power of two, where all lower bits are zero and flip to one.
package com.bank.service;
public class ComplementEdgeCases {
public static void main(String[] args) {
BitComplement bc = new BitComplement();
System.out.println("Complement of 0: " + bc.findComplement(0)); // 1
System.out.println("Complement of 1: " + bc.findComplement(1)); // 0
System.out.println("Complement of 5: " + bc.findComplement(5)); // 2
System.out.println("Complement of 8: " + bc.findComplement(8)); // 7
System.out.println("Complement of 7: " + bc.findComplement(7)); // 0
}
}
Complement of 0: 1
Complement of 1: 0
Complement of 5: 2
Complement of 8: 7
Complement of 7: 0
What are common mistakes?
The most common mistake is using the bitwise NOT operator (~) directly, which flips all 32 bits including leading zeros. Another mistake is not handling zero separately.
// WRONG: bitwise NOT flips all 32 bits
int complement = ~num; // includes leading zeros -> wrong answer
// CORRECT: build mask of the right width
int bitCount = 0;
int temp = num;
while (temp > 0) { bitCount++; temp >>= 1; }
int mask = (1 << bitCount) - 1;
int complement = num ^ mask;
How is this different from bitwise NOT (~)?
Bitwise NOT flips all 32 bits, including leading zeros. The complement within bit width only flips the meaningful bits. These produce very different results.
| Input | Binary | ~num (all 32) | Complement (width only) |
|---|---|---|---|
| 5 | 101 | -6 (flips all 32 bits) | 2 (010) |
| 8 | 1000 | -9 (flips all 32 bits) | 7 (0111) |
| 1 | 1 | -2 (flips all 32 bits) | 0 (0) |
System.out.println("~5 = " + (~5)); // -6
System.out.println("complement(5) = " + (5 ^ 0b111)); // 2
How would you apply this in a banking system?
At the National Bank of India, a legacy device stores account flags as compact binary numbers. A downstream system needs the inverted mirror flag. Rajesh measures the flag's width, builds an all-ones mask, and XORs once to produce the mirror flag without affecting higher bits.
package com.bank.service;
public class AccountFlagService {
public int invertFlag(int flag) {
if (flag == 0) return 1;
int bitCount = 0;
int temp = flag;
while (temp > 0) {
bitCount++;
temp >>= 1;
}
int mask = (1 << bitCount) - 1;
return flag ^ mask;
}
public static void main(String[] args) {
AccountFlagService service = new AccountFlagService();
int flag = 0b1010; // 10: active=1, verified=0, premium=1, locked=0
int mirror = service.invertFlag(flag);
System.out.println("Original flag: " + Integer.toBinaryString(flag));
System.out.println("Mirror flag: " + Integer.toBinaryString(mirror));
}
}
Original flag: 1010
Mirror flag: 101
What should a senior engineer know?
A senior engineer should know that Integer.highestOneBit(num) returns a value with only the highest set bit, and (highestOneBit << 1) - 1 gives the mask directly without a loop. They should also know that this technique is the basis for many bit manipulation tricks in competitive programming.
// One-liner mask construction (no loop)
int mask = (Integer.highestOneBit(num) << 1) - 1;
int complement = num ^ mask;
// Or using numberOfLeadingZeros
int mask2 = (1 << (32 - Integer.numberOfLeadingZeros(num))) - 1;
int complement2 = num ^ mask2;
Visual Overview
Example: num = 5 (binary: 101) Step 1: Find bit width 5 >> 1 = 2 (count=1) 2 >> 1 = 1 (count=2) 1 >> 1 = 0 (count=3) → bit width = 3 Step 2: Build mask mask = (1 << 3) - 1 = 8 - 1 = 7 = 111 in binary Step 3: XOR num: 1 0 1 mask: 1 1 1 XOR: 0 1 0 = 2 ← complement ┌──────────────────────────────────┐ │ num = 101 (5) │ │ mask = 111 (7) │ │ XOR = 010 (2) ← complement │ └──────────────────────────────────┘ Why not ~5? ~5 = 11111111111111111111111111111010 = -6 We only want to flip the 3 meaningful bits.
Key Takeaway
Complement of Base 10 Number asks me to flip every bit of a number, but only across the width the number actually uses, not the full 32 bits of an integer. The clean approach is to build an all-ones mask of the same width as the number and XOR once. XOR with ones flips every bit: 0 becomes 1 and 1 becomes 0.
I measure the width by right-shifting a copy of the number until it reaches zero, counting the shifts. Then I build the mask as (1 << bitCount) - 1 and XOR the number with it. The reason I limit the mask to the number's width is critical: if I flipped all 32 bits, the leading zeros would become ones, producing a huge or negative number.
The edge case of zero is handled separately because it has no set bits, and its complement is conventionally one. The common mistake is using bitwise NOT (~) directly, which flips all 32 bits and gives the wrong result.
At the National Bank of India, I used this to bridge a legacy device that stored account flags as compact binary numbers. A downstream system needed the inverted mirror flag with every used bit flipped. Measuring the width and XORing with a matched mask produced the mirror in one operation.
Remember one sentence: build an all-ones mask as wide as the number, XOR once, and you have the complement without touching the leading zeros.
---