CODEWITHSUNDEEP
c
webgenius
webgenius

Reputation: 904

Logic explanation required

My question is similar to the one here

The best answer for the question is:

int isNotZero(unsigned int n){
  n |= n >> 16;
  n |= n >> 8;
  n |= n >> 4;
  n |= n >> 2;
  n |= n >> 1;
  return n & 1;
};

Could anyone please explain me how the above algorithm works?

Upvotes: 0

Views: 89

Answers (1)

Chowlett
Chowlett

Reputation: 46677

n is a 32-bit integer. n |= n >> 16 takes the 16 highest bits and ensures that the equivalent bit in the lower 16 is set for each set bit in the higher 16; while maintaining any bits already set in the lower 16.

In this way, you now have a 16-bit integer which is non-zero precisely when the original 32-bit integer was. The following steps then similarly fold the number into 8 bits, then 4, then 2, then 1.

Finally, the last line checks if the lowest bit is set, which by the above tells you if the original number was non-zero.

Upvotes: 6

Related Questions