4 ms·

Moreover, I think that some answers are not doing what we should expect from the subject. For example the "Detect Multiple Of Two" detects powers of two, not mu

by fruneau 13y ago

Moreover, I think that some answers are not doing what we should expect from the subject. For example the "Detect Multiple Of Two" detects powers of two, not multiples.

deleted 13y ago
[deleted]
yajoe 13y ago
Agree on needing comments. My C++ is a bit rusty, but I think the code is in fact checking if the number is divisible by 2 (i.e. n % 2 == 0). I think it's using the bitwise and operator (single &) to AND each bit in n and (n-1) and then checking if the least significant bit is 1 or 0. The code would need to shift (<< or >>) to check if the number were a power of 2. I thought there was another bitwise NOT operator, not the !, but I think, and this is the part I'm hazy on after getting home, that the ! applied to an int is intended to flip each bit. Here's why: ------------ n = 6 = 110 n-1 = 5 = 101 n & (n-1) = 110 & 101 = 100 !(110) = 001 => true ------------ n = 5 = 101 n-1 = 100 n & (n-1) = 101 & 100 = 101 !(101) = 010 => false only if the least significant bit is used for logic decisions... this seems non-portable for some reason, just like using the ! as a bitwise NOT. It may actually be that ! only looks at the least significant bit, but I can't find c++ docs to say one way or another. Whatever the code actually does, this is exactly the kind of example to use as a poster child for adding just a few comments.
- ColinWright 13y ago
  The GP is correct, this is bit-twiddling code to test for a single bit being set in the int, and therefore being a power of 2, not simply a multiple of 2. Broadly speaking, and ignoring edge cases, if N is a power of 2 then it has a single bit set. Subtracting one unsets that bit, so the AND of N and (N-1) is zero. On the other hand, if N is not a power of two then subtracting 1 leaves the top bit still set, so the AND is non-zero. Therefore taking the boolean NOT gives the right answer. 00010000 Power of 2 00001111 N-1 -------- 00000000 -> 0 00010110 Non power of 2 00010101 N-1 -------- 00010100 -> Non 0 Thus power of 2 is NOT( N & (N-1) ). Your examples are wrong because "!" is not bit-wise NOT, but boolean NOT. !0 = True, !N = False when N is non-zero. It's actually wrong on the edge case of N=1, which is a power of 2.
  - yajoe 13y ago
    Thanks, you're right. I don't know why I would have ever thought "!" was bitwise... only on a Saturday night. It just goes to show that sleep is very important for interviews!

by fruneau 13y ago

Moreover, I think that some answers are not doing what we should expect from the subject. For example the "Detect Multiple Of Two" detects powers of two, not multiples.

deleted 13y ago

[deleted]

yajoe 13y ago

Agree on needing comments. My C++ is a bit rusty, but I think the code is in fact checking if the number is divisible by 2 (i.e. n % 2 == 0). I think it's using the bitwise and operator (single &) to AND each bit in n and (n-1) and then checking if the least significant bit is 1 or 0. The code would need to shift (<< or >>) to check if the number were a power of 2. I thought there was another bitwise NOT operator, not the !, but I think, and this is the part I'm hazy on after getting home, that the ! applied to an int is intended to flip each bit. Here's why: ------------ n = 6 = 110 n-1 = 5 = 101 n & (n-1) = 110 & 101 = 100 !(110) = 001 => true ------------ n = 5 = 101 n-1 = 100 n & (n-1) = 101 & 100 = 101 !(101) = 010 => false only if the least significant bit is used for logic decisions... this seems non-portable for some reason, just like using the ! as a bitwise NOT. It may actually be that ! only looks at the least significant bit, but I can't find c++ docs to say one way or another. Whatever the code actually does, this is exactly the kind of example to use as a poster child for adding just a few comments.

ColinWright 13y ago
The GP is correct, this is bit-twiddling code to test for a single bit being set in the int, and therefore being a power of 2, not simply a multiple of 2. Broadly speaking, and ignoring edge cases, if N is a power of 2 then it has a single bit set. Subtracting one unsets that bit, so the AND of N and (N-1) is zero. On the other hand, if N is not a power of two then subtracting 1 leaves the top bit still set, so the AND is non-zero. Therefore taking the boolean NOT gives the right answer. 00010000 Power of 2 00001111 N-1 -------- 00000000 -> 0 00010110 Non power of 2 00010101 N-1 -------- 00010100 -> Non 0 Thus power of 2 is NOT( N & (N-1) ). Your examples are wrong because "!" is not bit-wise NOT, but boolean NOT. !0 = True, !N = False when N is non-zero. It's actually wrong on the edge case of N=1, which is a power of 2.
- yajoe 13y ago
  Thanks, you're right. I don't know why I would have ever thought "!" was bitwise... only on a Saturday night. It just goes to show that sleep is very important for interviews!