testing if just one bit is set...

..rhavin grobert wrote:

guess you have a processor that can handle 32bit natively and you have
a 32-bit-int. im now looking for some *ultrafast* way to determine if
an int has more than one bit set. any ideas?

The following is based on an idiom in Hacker's Delight, by Henry S.
Warren, Jr., Addison Wesley, 2003. I've only considered it for two's
complement. If you need a lot of these very low-level shortcuts (or
just like reading about them), buy the book. It's a mind-bender.

bool multiple_bits_set(unsigned n) {
return n & (n - 1);
}

bool exactly_one_bit_set(unsigned n) {
return n && !multiple_bits_set(n);
}

#include <cassert>

int main() {

for (unsigned n = 1; n; n <<= 1) {
assert(exactly_one_bit_set(n));
}

assert(!exactly_one_bit_set(0));
assert(!exactly_one_bit_set(3));
assert(!exactly_one_bit_set(12));
}

Nov 6 '08 #6

Victor Bazarov

Salt_Peter wrote:

On Nov 6, 1:42 pm, ".rhavin grobert" <cl...@yahoo.dewrote:
>guess you have a processor that can handle 32bit natively and you have
a 32-bit-int. im now looking for some *ultrafast* way to determine if
an int has more than one bit set. any ideas?

an int is not necessarily 32 bits. That depends on the platform.
bitset has a member function count() which returns a count of bits
set.
Use that. If thats too slow for you, try release mode instead of
debug.

#include <iostream>
#include <bitset>

template< typename T >
bool checkbits(const std::bitset< sizeof(T) * 8 >& r)

What's the "8" for? Consider your own words "depends on the platform"
before giving your answer.

{
return (r.count() 1) ? true : false;

Wouldn't it be clearer to write

return r.count() 1;

?

}

Also, consider rewriting so that the type doesn't have to be explicitly
specified. Perhaps something like

template<typename Tbool checkbits(T t)
{
std::bitset<..whatever..r(t);
...

>
int main ()
{
int n(257);
std::bitset< sizeof(int) * 8 b(n);

Here it is again... What's the meaning of "8" here?

>
for (std::size_t i = b.size(); i 0; --i)
{
std::cout << b.test(i - 1);
if((i-1)%4 == 0)
std::cout << " ";
}
std::cout << std::endl;

if(checkbits< int >(b))
std::cout << "more than one bit set\n";
else
std::cout << "less than 2 bits set\n";
}

/*
0000 0000 0000 0000 0000 0001 0000 0000
result: less than 2 bits set
*/

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

Nov 6 '08 #7

Guy.Tristram

On Nov 6, 7:17*pm, Victor Bazarov <v.Abaza...@comAcast.netwrote:

Andrew Koenig wrote:
If n has an unsigned type (i.e. unsigned int or unsigned long), then (n&-n)
is equal to n unless n has more than one bit set.
So the expression you're looking for is n!=(n&-n)

Wow... *Does it work for any representation (two's complement, one's
complement, signed magnitude)?

There's a good page on this type of trick here:

http://realtimecollisiondetection.net/blog/?p=78

Guy

Nov 6 '08 #8

Victor Bazarov wrote:

Andrew Koenig wrote:
>".rhavin grobert" <cl***@yahoo.dewrote in message
news:ec**********************************@u29g200 0pro.googlegroups.com...

>>guess you have a processor that can handle 32bit natively and you have
a 32-bit-int. im now looking for some *ultrafast* way to determine if
an int has more than one bit set. any ideas?

If n has an unsigned type (i.e. unsigned int or unsigned long), then
(n&-n) is equal to n unless n has more than one bit set.
So the expression you're looking for is n!=(n&-n)

Wow... Does it work for any representation (two's complement, one's
complement, signed magnitude)?

Unsigned values don't vary in representation. "Two's complement, one's
complement, signed magnitude" come into play with signed representations
only.

--
Best regards,
Andrey Tarasevich

Nov 6 '08 #9

Juha Nieminen

Jeff Schwab wrote:

I've only considered it for two's complement.

Exactly how does two's complement representation kick in with unsigned
values?

Nov 6 '08 #10

Sana

On Nov 6, 3:09*pm, Andrey Tarasevich <andreytarasev...@hotmail.com>
wrote:

Victor Bazarov wrote:
Andrew Koenig wrote:
".rhavin grobert" <cl...@yahoo.dewrote in message
news:ec**********************************@u29g200 0pro.googlegroups.com....

>guess you have a processor that can handle 32bit natively and you have
a 32-bit-int. im now looking for some *ultrafast* way to determine if
an int has more than one bit set. any ideas?

If n has an unsigned type (i.e. unsigned int or unsigned long), then
(n&-n) is equal to n unless n has more than one bit set.
So the expression you're looking for is n!=(n&-n)

Wow... *Does it work for any representation (two's complement, one's
complement, signed magnitude)?

Unsigned values don't vary in representation. "Two's complement, one's
complement, signed magnitude" come into play with signed representations
only.

Assuming a 32 bit system, and let n be an unsigned int of value
0xFFFFFFFF (all bits set)
What would be the value of -n in the expression n & -n?

Thanks,
Sana

Nov 6 '08 #11

Juha Nieminen wrote:

Jeff Schwab wrote:
>I've only considered it for two's complement.

Exactly how does two's complement representation kick in with unsigned
values?

Are you asking why the representation is relevant? As far as I know,
all of the representations allowed by the Standard are equivalent for
purposes of this discussion. The only one I've really considered is
two's complement, though. That doesn't mean I think there's any
particular problem with the other allowed representations, just that I
don't know enough about them to know whether there are any gotchas.

Nov 6 '08 #12

Sana wrote:

Assuming a 32 bit system, and let n be an unsigned int of value
0xFFFFFFFF (all bits set)
What would be the value of -n in the expression n & -n?

'-n' in this case would be '1' (0x00000001). See 5.3/7: "The negative of
an unsigned quantity is computed by subtracting its value from 2^n,
where n is the number of bits in the promoted operand".

--
Best regards,
Andrey Tarasevich

Nov 6 '08 #13

Jeff Schwab wrote:

>
Are you asking why the representation is relevant? As far as I know,
all of the representations allowed by the Standard are equivalent for
purposes of this discussion. The only one I've really considered is
two's complement, though. That doesn't mean I think there's any
particular problem with the other allowed representations, just that I
don't know enough about them to know whether there are any gotchas.

Well, unsigned values in C++ have one and only one [allowed]
representation. Which is why some people might find any mention of
"other representations" to be confusing (equivalent or not).

--
Best regards,
Andrey Tarasevich

Nov 6 '08 #14

Salt_Peter

On Nov 6, 3:01 pm, Victor Bazarov <v.Abaza...@comAcast.netwrote:

Salt_Peter wrote:
On Nov 6, 1:42 pm, ".rhavin grobert" <cl...@yahoo.dewrote:
guess you have a processor that can handle 32bit natively and you have
a 32-bit-int. im now looking for some *ultrafast* way to determine if
an int has more than one bit set. any ideas?

an int is not necessarily 32 bits. That depends on the platform.
bitset has a member function count() which returns a count of bits
set.
Use that. If thats too slow for you, try release mode instead of
debug.

#include <iostream>
#include <bitset>

template< typename T >
bool checkbits(const std::bitset< sizeof(T) * 8 >& r)

What's the "8" for? Consider your own words "depends on the platform"
before giving your answer.

Couldn't agree with you more, what do you suggest? sizeof(char) ?
The n!=(n&-n) solution is better, but for the sake of platform...

>
{
return (r.count() 1) ? true : false;

Wouldn't it be clearer to write

return r.count() 1;

?

}

Also, consider rewriting so that the type doesn't have to be explicitly
specified. Perhaps something like

template<typename Tbool checkbits(T t)
{
std::bitset<..whatever..r(t);
...

int main ()
{
int n(257);
std::bitset< sizeof(int) * 8 b(n);

Here it is again... What's the meaning of "8" here?

for (std::size_t i = b.size(); i 0; --i)
{
std::cout << b.test(i - 1);
if((i-1)%4 == 0)
std::cout << " ";
}
std::cout << std::endl;

if(checkbits< int >(b))
std::cout << "more than one bit set\n";
else
std::cout << "less than 2 bits set\n";
}

/*
0000 0000 0000 0000 0000 0001 0000 0000
result: less than 2 bits set
*/

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

Nov 6 '08 #15

Andrey Tarasevich wrote:

Well, unsigned values in C++ have one and only one [allowed]
representation. Which is why some people might find any mention of
"other representations" to be confusing (equivalent or not).

We're not only discussing unsigned values.

The OP was specifically asking about the number of bits set in a 32-bit
int; by definition, that depends on the representation. We have instead
chosen to talk mostly about unsigned types, but operations involving
types of differing signedness can still result in signed values. For
example, given an unsigned int n, it is implementation-defined whether
the result of the following expression is signed:

n - 3L;

The code I posted included functions that accepted only unsigned ints,
but it also included the mixed expression n-1 and conversions from
unsigned to bool. Everything worked out OK there because the signed 1
was implicitly converted to unsigned, but at this low level of
abstraction, it becomes (IMO) the programmer's responsibility to at
least be aware of the representations involved.

Nov 6 '08 #16

Salt_Peter wrote:

On Nov 6, 3:01 pm, Victor Bazarov <v.Abaza...@comAcast.netwrote:
>Salt_Peter wrote:
>>On Nov 6, 1:42 pm, ".rhavin grobert" <cl...@yahoo.dewrote:
guess you have a processor that can handle 32bit natively and you have
a 32-bit-int. im now looking for some *ultrafast* way to determine if
an int has more than one bit set. any ideas?
an int is not necessarily 32 bits. That depends on the platform.
bitset has a member function count() which returns a count of bits
set.
Use that. If thats too slow for you, try release mode instead of
debug.
#include <iostream>
#include <bitset>
template< typename T >
bool checkbits(const std::bitset< sizeof(T) * 8 >& r)
What's the "8" for? Consider your own words "depends on the platform"
before giving your answer.

Couldn't agree with you more, what do you suggest? sizeof(char) ?

sizeof(char) == 1, by definition. Below is a portable, MPL-style
metafunction.

#include <limits>

template<typename T>
class bit_count {

typedef std::numeric_limits<Tlimits;

public:

struct type {
enum { value = limits::digits + limits::is_signed };
};
};

#include <iostream>

int main() {
std::cout << bit_count<char>::type::value << '\n';
}

Nov 6 '08 #17

On Nov 6, 10:55 pm, Jeff Schwab <j...@schwabcenter.comwrote:

Juha Nieminen wrote:
Jeff Schwab wrote:
I've only considered it for two's complement.

Exactly how does two's complement representation kick in
with unsigned values?

Are you asking why the representation is relevant? As far as
I know, all of the representations allowed by the Standard are
equivalent for purposes of this discussion.

Yes and no. For signed values, the bit pattern of -n will
depend on the representation. For unsigned values, the standard
defines -i to be 2^n-i (where n is the number of value bits in
the unsigned). Which by a curious bit of chance(:-)) just
happens to correspond to what you'd get for 2's complement
signed values.

The only one I've really considered is two's complement,
though. That doesn't mean I think there's any particular
problem with the other allowed representations, just that I
don't know enough about them to know whether there are any
gotchas.

On thing is immediately certain, the bit pattern of -n will
depend on the representation if the type is signed. Which means
that it probably will not work.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Nov 7 '08 #18

On Nov 6, 11:47 pm, Jeff Schwab <j...@schwabcenter.comwrote:

Andrey Tarasevich wrote:
Well, unsigned values in C++ have one and only one [allowed]
representation. Which is why some people might find any
mention of "other representations" to be confusing
(equivalent or not).

We're not only discussing unsigned values.

The OP was specifically asking about the number of bits set in
a 32-bit int; by definition, that depends on the
representation.

Of course, the obvious solution is to cast to unsigned, and then
procede. Except that if he really is concerned with signed
values, casting to unsigned may change the bit pattern (and thus
the number of bits). A reinterpret_cast involving references
might do the trick (to make the compiler access the value as if
it were unsigned), although even there, on at least one machine,
unsigned is implemented by simply masking out the sign bit (i.e.
UINT_MAX == INT_MAX).

Given that the original poster specified 32 bits, however, I
rather suspect that total portability wasn't a concern; all of
the 32 bit machines I know today use 2's complement, where
converting an int to an unsigned doesn't change the bit pattern.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Nov 7 '08 #19

blargg

In article <ph******************@bgtnsc05-news.ops.worldnet.att.net>,
"Andrew Koenig" <ar*@acm.orgwrote:

".rhavin grobert" <cl***@yahoo.dewrote in message
news:ec**********************************@u29g2000 pro.googlegroups.com...

guess you have a processor that can handle 32bit natively and you have
a 32-bit-int. im now looking for some *ultrafast* way to determine if
an int has more than one bit set. any ideas?

If n has an unsigned type (i.e. unsigned int or unsigned long), then (n&-n)
is equal to n unless n has more than one bit set.
So the expression you're looking for is n!=(n&-n)

What about

(n-1)&n

which probably involves fewer operations (negate+and+compare versus
subtract+and)? Non-zero if more than one bit is set.

Nov 7 '08 #20

Hendrik Schober

Salt_Peter wrote:

On Nov 6, 3:01 pm, Victor Bazarov <v.Abaza...@comAcast.netwrote:
>Salt_Peter wrote:
[...]

>>template< typename T >
bool checkbits(const std::bitset< sizeof(T) * 8 >& r)
What's the "8" for? Consider your own words "depends on the platform"
before giving your answer.

Couldn't agree with you more, what do you suggest? [...]

'CHAR_BIT' from <climit>?

Schobi

Nov 7 '08 #21

blargg

James Kanze wrote:
[...]

For unsigned values, the standard
defines -i to be 2^n-i (where n is the number of value bits in
the unsigned). Which by a curious bit of chance(:-)) just
happens to correspond to what you'd get for 2's complement
signed values.

Not just because two's complement is common and they wanted to allow use
of the native negate instruction, but because two's complement is the most
natural representation. Ignoring two's complement, defining -unsigned in
that way ensures things like

-x == 0U-x
x-y == x+-y
-(-x) == x

etc., where x and y are unsigned.

Nov 7 '08 #22

James Kanze wrote:

On Nov 6, 11:47 pm, Jeff Schwab <j...@schwabcenter.comwrote:
>Andrey Tarasevich wrote:
>>Well, unsigned values in C++ have one and only one [allowed]
representation. Which is why some people might find any
mention of "other representations" to be confusing
(equivalent or not).

>We're not only discussing unsigned values.

Of course, the obvious solution is to cast to unsigned, and then
procede. Except that if he really is concerned with signed
values, casting to unsigned may change the bit pattern (and thus
the number of bits). A reinterpret_cast involving references
might do the trick (to make the compiler access the value as if
it were unsigned),

Is that UB? It reminds me of the old "access the other member of the
union" trick.

although even there, on at least one machine,
unsigned is implemented by simply masking out the sign bit (i.e.
UINT_MAX == INT_MAX).

What machine is that? I don't doubt that such platforms exist, but that
sounds more exotic than anything I've targeted.

Nov 7 '08 #23

On Nov 7, 12:59 pm, Jeff Schwab <j...@schwabcenter.comwrote:

James Kanze wrote:
On Nov 6, 11:47 pm, Jeff Schwab <j...@schwabcenter.comwrote:
Andrey Tarasevich wrote:
Well, unsigned values in C++ have one and only one [allowed]
representation. Which is why some people might find any
mention of "other representations" to be confusing
(equivalent or not).

We're not only discussing unsigned values.
Of course, the obvious solution is to cast to unsigned, and
then procede. Except that if he really is concerned with
signed values, casting to unsigned may change the bit
pattern (and thus the number of bits). A reinterpret_cast
involving references might do the trick (to make the
compiler access the value as if it were unsigned),

Is that UB? It reminds me of the old "access the other member
of the union" trick.

Yes and no. Casting a pointer or a reference is the
"officially" sanctionned way of type punning, but of course, you
don't get any guarantees with regards to the meaning of the
results in general. In this one particular case, you are
guaranteed that 1) the size of a signed integral type and its
corresponding unsigned is the same, and 2) that non-negative
values will have the same representation. So unless the sign
bit acts funny, you should be OK. (The C standard more or less
sanctions it, too, in that it allows you to pass signed integers
to match a "%x" format specifier.)

although even there, on at least one machine, unsigned is
implemented by simply masking out the sign bit (i.e.
UINT_MAX == INT_MAX).

What machine is that? I don't doubt that such platforms
exist, but that sounds more exotic than anything I've
targeted.

Unisys MCP. It's an interesting machine; it descends from the
old Burroughs line of machines, uses a stack instead of
registers, and has a tagged architecture; there's only one add,
sub, etc. instruction, which works for floating point or
integral values. I've not got access to one to do any testing,
but given the way it works, I suspect that an overflow in
integral arithmetic could lead to some very strange behavior.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Nov 7 '08 #24

On Nov 7, 12:01 pm, blargg....@gishpuppy.com (blargg) wrote:

James Kanze wrote:

[...]
but because two's complement is the most
natural representation.

What does "the most natural representation" mean? I would have
thought that the most natural representation would be base 10
(which is forbidden for ints).

2's complement has one very big problem: - INT_MIN isn't
representable. 1's complement and signed magnitude have to
consider signed 0, but IMHO, that's a lesser problem; in
addition, it can be handled by hardware in a transparent manner.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Nov 7 '08 #25

blargg

James Kanze wrote:

On Nov 7, 12:01 pm, blargg....@gishpuppy.com (blargg) wrote:
James Kanze wrote:

[...]
but because two's complement is the most
natural representation.

What does "the most natural representation" mean?

Two's complement is the natural way to represent negative values, since
things like add, subtract, multiply (both by a power of two using a shift,
and by an arbitrary value) can use the same hardware as the unsigned
equivalents.

[...]

2's complement has one very big problem: - INT_MIN isn't
representable.

[...]

How is this a big problem? Since trying to generate a value outside the
range of a signed type is UB, one could just treat the most negative as UB
by making INT_MIN == -INT_MAX.

Nov 8 '08 #26

On Nov 8, 12:02*pm, blargg....@gishpuppy.com (blargg) wrote:

James Kanze wrote:
On Nov 7, 12:01 pm, blargg....@gishpuppy.com (blargg) wrote:
James Kanze wrote:

[...]
but because two's complement is the most natural
representation.

What does "the most natural representation" mean?

Two's complement is the natural way to represent negative
values, since things like add, subtract, multiply (both by a
power of two using a shift, and by an arbitrary value) can use
the same hardware as the unsigned equivalents.

In other words, it's not the most natural, it's the cheapest.

[...]2's complement has one very big problem: - INT_MIN isn't
representable.

[...]

How is this a big problem? Since trying to generate a value
outside the range of a signed type is UB, one could just treat
the most negative as UB by making INT_MIN == -INT_MAX.

To begin with, you can't write the value directly as an integral
literal. And you have to special case it in a lot of cases.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Nov 9 '08 #27

Andrew Koenig

"Victor Bazarov" <v.********@comAcast.netwrote in message
news:ge**********@news.datemas.de...

>If n has an unsigned type (i.e. unsigned int or unsigned long), then
(n&-n) is equal to n unless n has more than one bit set.
So the expression you're looking for is n!=(n&-n)

Wow... Does it work for any representation (two's complement, one's
complement, signed magnitude)?

Just 2's complement -- but that's what everyone uses these days anyway.

Nov 14 '08 #28

Andrew Koenig

"Andrey Tarasevich" <an**************@hotmail.comwrote in message
news:ge**********@aioe.org...

Unsigned values don't vary in representation. "Two's complement, one's
complement, signed magnitude" come into play with signed representations
only.

The question is whether the meaning of -n depends on the representation of
signed values.

Nov 14 '08 #29

Andrew Koenig wrote:

>
>Unsigned values don't vary in representation. "Two's complement, one's
complement, signed magnitude" come into play with signed representations
only.

The question is whether the meaning of -n depends on the representation of
signed values.

And the answer is no. Within the pre-condition of 'n' being of type
'unsigned int' or 'unsigned long' (set in your original message) it
doesn't. The meaning of unary '-' for these types is defined by the
language specification without any dependency on signed representations,
meaning that the result is always the same regardless of signed
representation used by the implementation.

--
Best regards,
Andrey Tarasevich

Nov 14 '08 #30

On Nov 14, 6:48*pm, "Andrew Koenig" <a...@acm.orgwrote:

"Victor Bazarov" <v.Abaza...@comAcast.netwrote in message

news:ge**********@news.datemas.de...

If n has an unsigned type (i.e. unsigned int or unsigned
long), then (n&-n) is equal to n unless n has more than one
bit set. So the expression you're looking for is n!=(n&-n)
Wow... *Does it work for any representation (two's
complement, one's complement, signed magnitude)?

Just 2's complement -- but that's what everyone uses these
days anyway.

Andy, what's up? In your posting, you specifically said "If n
has an unsigned type". And you know very well that the standard
defines - for unsigned types exactly.

And not everyone uses 2's complement. There are at least two
architectures being sold today that don't: one with 36 bit 1's
complement, and another with 48 bit signed magnitude. (Since
they're mainframes, a lot of programmers don't see them, but
they are there.)

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Nov 14 '08 #31

blargg

James Kanze wrote:

On Nov 14, 6:48=A0pm, "Andrew Koenig" <a...@acm.orgwrote:
"Victor Bazarov" <v.Abaza...@comAcast.netwrote in message
news:ge**********@news.datemas.de...
>If n has an unsigned type (i.e. unsigned int or unsigned
>long), then (n&-n) is equal to n unless n has more than one
>bit set. So the expression you're looking for is n!=(n&-n)
>
Wow... Does it work for any representation (two's
complement, one's complement, signed magnitude)?
Just 2's complement -- but that's what everyone uses these
days anyway.

Andy, what's up? In your posting, you specifically said "If n
has an unsigned type". And you know very well that the standard
defines - for unsigned types exactly.

Presumably "works for any representation" meant that things OTHER than
unsigned were being considered, since unsigned types use two's complement
and nothing else. And it's true, said expression does NOT work for
representations other than two's complement. Since almost everything uses
two's complement these days, said expression will thus work even for
signed types on almost everything.

Nov 15 '08 #32