int findComplement(int num) {
int mask = num;
mask = mask >> 1;
mask = mask >> 2;
mask = mask >> 4;
mask = mask >> 8;
mask = mask >> 16;
return num ^ mask;
}
maybe fewest operations


@NoAnyLove To understand the solution, we need to go backwards. The aim is to xor the given number with a mask. The mask should contain all 1s in its rightmost bits. However, the number of rightmost bits is important. In the case of 5(101), for example, the number of rightmost bits must be 3, since 5 uses 3 rightmost bits. The mask must be 111 for 5(101). When we xor 111 with 101, we will get 010. As another example, the mask will be 111111 for 38(100110)
So the problem boils down to generating the mask. Let's think about 8bit numbers. We can later extend the same logic to 32bit integers. I will count the bits from right to left, starting with 1.
The largest positive numbers represented by 8 bits will set 7th bit. 64(01000000) is the largest positive number represented by 8 bits, which has the most number of 0s. It is important for our explanation since we must turn all those 0s into 1s.
The first operation,
mask = mask>>1;
will set the 6th bit. So,mask
will become (01100000). Now, we know that the 7th and 6th bits are set, we can safely shift themask
to right by not 1 but 2 bits.mask = mask>>2;
will now set the 5th and 4th bits. By the same reason, we can now shift themask
to right by not 1, 2 or 3 but 4 bits. That is the threshold for 8bit numbers. We do not need to shift more.For 32bit integers, the shift operations should continue until reaching to 16. For 64bit longs, that will be 32.



@bertkellerman Hmm, I hadn't even thought about that. Well, the "normal" complement operation is still different from the one requested here, so I think it's ok. But I agree that it's better to not use it at all.

@NoAnyLove
mask = mask >> 1
will set the first left two bits to be 1,mask = mask >> 2
will set the first left four bits to be 1,
mask = mask >> 4
will set the first left 8 bits to be 1, ... , at last, all the bits will be 1.
