hmm, what does it do?

[puzzlecracker]

#define BLACKBOX(x) ((x)&((x)-1))

 

[Jay Nabonne]

#define BLACKBOX(x) ((x)&((x)-1))

Some empirical analysis:

1 -> 0
2 -> 0
3 -> 2
4 -> 0
5 -> 4
6 -> 4
7 -> 6
8 -> 0
9 -> 8
10 -> 8
11 -> 10
12 -> 8
13 -> 12
14 -> 12
15 -> 14
16 -> 0

Looks like it could be a test for "power of 2" (result is 0 or non-zero).

- Jay

 

[Andrea Sini]

#define BLACKBOX(x) ((x)&((x)-1))

What does it do...? Not C++...Deprecated, I would say.

Anyway, you are the puzzle cracker !!! Tell us...

Andrea

 

[Jerry Coffin]

#define BLACKBOX(x) ((x)&((x)-1))

Perhaps it would help to get started if you thought of the output as a
boolean (i.e. paid attention only to zero vs. non-zero results).

 

[Matt Bitten]

int pwr2(int x); // Returns the highest power of 2
// that divides x

assert(BLACKBOX(x) == x - pwr2(x));

 

[Pan Jiaming]

Yes!
BLACKBOX(x) return zero if and only if there is only one '1' in x, that is,
x is "power of 2"

 

[Pan Jiaming]

Yes!
BLACKBOX(x) return zero if and only if there is only one '1' in x, that is,
x is "power of 2"

 

[Heinz Ozwirk]

#define BLACKBOX(x) ((x)&((x)-1))

That's part of a piece of code made famous by Edsgar Dijkstra. Translated to C++ it looks like this

int foo(int x)
{
int n = 0;
while (x)
{
++n;
x &= x-1;
}
return n;
}

Now guess what this one does. If you can solve one, you can probably solve the other, too.

Heinz

 

[Chris Croughton]

Yes!
BLACKBOX(x) return zero if and only if there is only one '1' in x, that is,
x is "power of 2"

a) Please don't top-post, write your answer below the quoted text (and
trim that to just the part you are answering).

b) Since when has zero been a power of 2 (BLACKBOX(0) is zero as well)?

c) Look at what it does in binary:

00000 & 11111 -> 00000
00001 & 00000 -> 00000
00010 & 00001 -> 00000
00011 & 00010 -> 00010
00100 & 00011 -> 00000
00101 & 00100 -> 00100
00110 & 00101 -> 00100
00111 & 00110 -> 00110
01000 & 00111 -> 00000
01001 & 01000 -> 01000
01010 & 01001 -> 01000
01011 & 01010 -> 01010
01100 & 01011 -> 01000
01101 & 01100 -> 01100
01110 & 01101 -> 01100
01111 & 01110 -> 01110
10000 & 01111 -> 00000

Now, what is it doing?

Chris C

 

[Pan Jiaming]

This is one question in Microsoft ATC recruiting test in China this year.

"Heinz Ozwirk" <[email protected]> ????

#define BLACKBOX(x) ((x)&((x)-1))

That's part of a piece of code made famous by Edsgar Dijkstra. Translated to
C++ it looks like this

int foo(int x)
{
int n = 0;
while (x)
{
++n;
x &= x-1;
}
return n;
}

Now guess what this one does. If you can solve one, you can probably solve
the other, too.

Heinz

 

[Melody]

Now guess what this one does. If you can solve one, you can probably solve
the other, too.

Counts the number of 1s in the binary expression of the number?

 

[Howard]

#define BLACKBOX(x) ((x)&((x)-1))

It defines a macro called BLACKBOX with a parameter x, which expands as a
bitwise AND of x with x-1.

What do I win?

Actually, the above is only strictly true for the built-in numeric types.
For a user-defined class, I believe it expands as

x.operator&(x.operator-(1))

(I'm terrible at this crap. But I'm correct, right?)

So what it "does" depends largely upon what the type of x is, and how the
operators & and - for that type are defined.

-Howard

 

[Matt Bitten]

"foo" counts the number of 1's in the binary representation.
The original problem turns the right-most 1 to a 0.