Binary Magic

Akrabul Islam
2 min readNov 21, 2020

First of all, I am going to list up these problems because I want to keep this as a note in my own way. Besides these problems will improve to solve specif problem.

  1. 1’s and 2’s complement of a Binary Number
  2. Gray Code
  3. Bit Tricks for Competitive Programming
  4. Bits manipulation
  5. Bitwise OR (|) of a range
  6. Bitwise AND (&) of a range
  7. Builtin functions of GCC compiler
  8. C++ Bit set and its application
  9. Calculate XOR from 1 to n
  10. Check if a number has two adjacent set bits
  11. Check if bitwise AND of any subset is the power of two
  12. Check if n is divisible by a power of 2
  13. 1’s and 2’s complement of a Binary Number

1. 1’s and 2’s complement of a Binary Number

The ones’ complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number.

  • 1’s complement of “0111” is “1000”
  • 1’s complement of “1100” is “0011”

2’s complement of a binary number is adding 1 to its 1’s complement.

  • 2’s complement of “0111” is “1001”
  • 2’s complement of “1100” is “0100”

Another way to find 2’s complement is starting from LSB(Least Significant Bit) go left and toggle the bit until we found a 0 and finally change 0 to 1.

C++ Implementation :

int n = 7;
int one_s_complement = 0;
for(int i=0; i<32; i++){ //Integer is 32 bit check from 0 to 31
if(!(n&(1<<i))){ //check if the bit is 0 then we add pow(2,i)
one_s_complement += (1<<i);
}
}
cout<<"The one's complement is : "<< one_s_complement <<endl;
int two_s_complement = one_s_complement + 1;
cout<<"The two's complement is : "<< two_s_complement <<endl;
Output : The one's complement is : -8
The two's complement is : -7

We can see that the 1’s complement is the opposite and 1 greater than the actual number. On the other hand, the two’s complement is the opposite sign and the same value of the actual number. The negative number is represented in 2’s complement form.

int n = 10;
int one_s_complement = ~n; //bit wise not same as 1’s complement

cout<<"The one's complement is : "<< one_s_complement <<endl;
int two_s_complement = one_s_complement + 1;cout<<"The two's complement is : "<< two_s_complement <<endl;Output :The one's complement is : -8
The two's complement is : -7

--

--