ISRO Question

Can someone please explain me this program??
What does (num<<i&1<<15 ) ? 1:0) mean ??

So,
1 << 15 is the Most significant set bin in a 16 bit integer, i.e. - 1000000000000000.
So a bitwise & operation with such value will output 1 (decimal) is and only if the number has MSB set. ex 2 & (1 << 15) will output 0 (as per logic And truth table) as 2 = 000…10 (16 bit representation).
In the program the binary of 2 will be shifted left 16 times and whenever MSB bit representation of this will be 1, it will print one. So in the next iteration 2 will be = 000…100, then again in next iteration, it will be 000…1000 and so on.
So eventually it is checking for MSB set bit and outputting accordingly. Thus the answer = binary equivalent.

(Here, number 2 is taken just as an example. You can try with other numbers as well)

1 Like

The program prints the binary equivalent of num. It uses the bitwise operator & as well as the left shift <<.

If you aren’t sure what bitwise AND is, I recommended looking it up. But in brief, the bitwise AND operator takes two numbers and compares each bit in their binary representation. It returns 1 if both the bits are 1 and 0 otherwise. The resulting binary number is returned as a decimal number. For example:-

int a = 6; // 6 is 110 in binary
int b = 3; // 3 is 011 in binary
printf("%d", (a&b)); // returns 2 as 110 & 011 is 010 which is 2 in decimal

The left shift n << i takes a number n and “shifts” it’s binary representation to the left by i. For example:-

int a = 5; // 5 is 101 in binary
printf("%d", (a<<1)); // shifts 101 one place to the left to get 1010 which is 10

Also, the ? 1:0 is the ternary operator, it’s a shortcut for the if statement. It means if num << i & 1 << 15, output 1 otherwise, output 0. Perhaps this will be helpful.

Now let’s analyse the program. Let’s say we input num as 3, which is 11 in binary. Then it sets i=0 and loops from i=0 till i=15 and gives out 1 if the bitwise AND of num<<i and 1<<15 is true. Here, 1<<15 will be 1000000000000000, and the num << i & 1 << 15 does the following:-

0000000000000011 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000000000000110 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000000000001100 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000000000011000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000000000110000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000000001100000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000000011000000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000000110000000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000001100000000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000011000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0000110000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0001100000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0011000000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal
0110000000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal
1100000000000000 & 1000000000000000 = 1000000000000000 or 32768 in decimal
1000000000000000 & 1000000000000000 = 1000000000000000 or 32768 in decimal

Basically, it checks whether the 216th place in the binary expansion of num is 1, if so it returns 216, otherwise 0. Then it left shifts num by 1, and checks again (effectively checking the 215th place of num) and so on. The (num << i & 1 << 15) ? 1:0 returns 1 if the output of num << i & 1 << 15 is not 0, so,

0000000000000011 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000000000000110 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000000000001100 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000000000011000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000000000110000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000000001100000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000000011000000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000000110000000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000001100000000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000011000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0000110000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0001100000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0011000000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
0110000000000000 & 1000000000000000 = 0000000000000000 or 0     in decimal ? 1:0 is 0
1100000000000000 & 1000000000000000 = 1000000000000000 or 32768 in decimal ? 1:0 is 1
1000000000000000 & 1000000000000000 = 1000000000000000 or 32768 in decimal ? 1:0 is 1

And so this gives us as the output the binary representation of 3, 0000000000000011 ! :smiley:

You can see that this works for any number. Also, some similar code is given here, you should check it out.

3 Likes