By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,305 Members | 1,718 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,305 IT Pros & Developers. It's quick & easy.

hmm, what does it do?

P: n/a
#define BLACKBOX(x) ((x)&((x)-1))

Jul 23 '05 #1
Share this Question
Share on Google+
12 Replies


P: n/a
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
Jul 23 '05 #2

P: n/a
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
Jul 23 '05 #3

P: n/a
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.

Jul 23 '05 #4

P: n/a
int pwr2(int x); // Returns the highest power of 2
// that divides x

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

Jul 23 '05 #5

P: n/a
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

Jul 23 '05 #6

P: n/a
"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
Jul 23 '05 #7

P: n/a
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


Jul 23 '05 #8

P: n/a
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
Jul 23 '05 #9

P: n/a
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
Jul 23 '05 #10

P: n/a

"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?
Jul 23 '05 #11

P: n/a

"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


Jul 23 '05 #12

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

Jul 23 '05 #13

This discussion thread is closed

Replies have been disabled for this discussion.