CODEWITHSUNDEEP
cbit-manipulationbitwise-operators
n00bcoder123
n00bcoder123

Reputation: 119

What does this condition written in bitwise operators really do?

What does the following condition effectively check in C :

if(a & (1<<b))

I have been wracking my brains but I can't find a pattern. Any help? Also I have seen this used a lot in competitive programming, could anyone explain when and why this is used?

Upvotes: 1

Views: 84

Answers (3)

razz
razz

Reputation: 10120

Lets say for example a = 12 (binary: 1100) and you want to check that the third bit (binaries are read from right to left) is set to 1, to do that you can use & bitwise operator which work as following:

1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
1 & 1 = 1

To check if the third bit in a is set to 1 we can do:

1100
0100 &
------
0100 (4 in decimal) True

if a = 8 (binary: l000) on the other hand:

1000
0100 &
------
0000 (0 in decimal) False

Now to get the 0100 value we can right shift 1 by 2 (1 << 2) wich will append two zeros from the right and we'll get 100, in binaries left trailing zeros doesn't change the value so 100 is the same as 0100.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726987

In mathematical terms, this condition verifies if a's binary representation contains 2b. In terms of bits, this checks if b's bit of a is set to 1 (the number of the least significant bit is zero).

Recall that shifting 1 to the left by b positions produces a mask consisting of all zeros and a single 1 in position b counting from the right. A value of this mask is 2b.

When you perform a bitwise "AND" with such a mask, the result would be non-zero if, and only if, a's binary representation contains 2b.

Upvotes: 1

Degustaf
Degustaf

Reputation: 2670

It is checking whether the bth bit of a is set.

1<<b will shift over a single set bit b times so that only one bit in the bth position is set.

Then the & will perform a bitwise and. Since we already know the only bit that is set in 1<<b, either it is set in a, in which case we get 1<<b, or it isn't, in which case we get 0.

Upvotes: 4

Related Questions