0

I was going through the best solution of problem MAXCOUNT and found few lines which i didn't understand.

Codechef Problem and the Best Solution submitted

While I was reading the code to observe the approach, I encountered these lines at the top of code:

#define isSet(n) flags[n>>5]&(1<<(n&31))
#define unset(n) flags[n>>5] &= ~(1<<(n&31))
#define set(n) flags[n>>5]|=(1<<(n&31))

I have no idea what is the significance of using these lines.
Can anyone please explain these lines and why are they used?

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
Rishabh Prasad
  • 349
  • 1
  • 3
  • 13

1 Answers1

3

It looks like it is referring to an array of bits stored as integers. n >> 5 means divide it by 32, and there's 32 bits in an int so that indexes the array. Then the right hand side uses the remainder (the bit pattern of 31 is is 0b11111 meaning the and operation with it will filter out all the rest of the bits, leaving just the five least significant ones - which happens to match the remainder after dividing by 32) to find the specific bit it is interested in (1 << n makes a one-bit mask in position n, and the & operator filters out everything but that).

Unset uses ~, which inverts the mask - clearing the bit, leaving the rest the same. set uses the bitwise or operator, which sets a single bit.

So they are just convenience macros for working with individual bits in an array of integers.

Adam D. Ruppe
  • 25,382
  • 4
  • 41
  • 60
  • Nice answer. Maybe you could add that the bit pattern of 31 is `0b11111`, hence `n & 31` returns the five least significant bits of `n`. – 5gon12eder Dec 21 '14 at 18:56
  • Yes, indeed, I'll add that. As a general rule, any power of two is a single bit. A power of two minus one is all the bits to the right of that. This beautifully happens to match the remainder if you divided by that power of two (similarly to how in decimal numbers, if you divide by ten, the remainder will be the last digit on the right). It isn't generally true that & and remainders are the same, but it is in this case which is nice when working with bits like the author is here. – Adam D. Ruppe Dec 21 '14 at 19:03