hmm, what does it do?

[puzzlecracker]

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

[Jay Nabonne]

On Mon, 21 Feb 2005 12:54:26 -0800, puzzlecracker wrote:

#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]

puzzlecracker wrote:

#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]

puzzlecracker wrote:

#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).

--
Later,
Jerry.

The universe is a figment of its own imagination.

[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"

"Jay Nabonne" <ja*********@sonicNOSPAM.com> ????
news:pa****************************@sonicNOSPAM.co m...

On Mon, 21 Feb 2005 12:54:26 -0800, puzzlecracker wrote:

#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

[Heinz Ozwirk]

"puzzlecracker" <ir*********@gmail.com> schrieb im Newsbeitrag news:11**********************@l41g2000cwc.googlegr oups.com...

#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

[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"

"Jay Nabonne" <ja*********@sonicNOSPAM.com> ????
news:pa****************************@sonicNOSPAM.co m...

On Mon, 21 Feb 2005 12:54:26 -0800, puzzlecracker wrote:

#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

[Chris Croughton]

On Tue, 22 Feb 2005 16:56:08 +0800, Pan Jiaming
<ja**@mails.tsinghua.edu.cn> wrote:

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" <ho**********@arcor.de> ????
news:42***********************@newsread4.arcor-online.net...
"puzzlecracker" <ir*********@gmail.com> schrieb im Newsbeitrag
news:11**********************@l41g2000cwc.googlegr oups.com...

#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]

"Heinz Ozwirk" <ho**********@arcor.de> wrote in message
news:421afabc$0$13221That's part of

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]

"puzzlecracker" <ir*********@gmail.com> wrote in message
news:11**********************@l41g2000cwc.googlegr oups.com...

#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.