testing if just one bit is set...

[.rhavin grobert]

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?

 

[Andrew Koenig]

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)

 

[Salt_Peter]

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)
{
return (r.count() > 1) ? true : false;
}

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

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
*/

 

[Guy.Tristram]

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

 

[Andrey Tarasevich]

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.

 

[Juha Nieminen]

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

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

 

[Sana]

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

 

[Andrey Tarasevich]

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

 

[Andrey Tarasevich]

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

 

[Salt_Peter]

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

 

[James Kanze]

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]

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.

 

[Kai-Uwe Bux]

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.

For the OP, that would work too. Which one is faster, only measurement can
show.

As for the two methods, n & -n has the nice feature of having all but the
lowest order bit in n equal to 0. Thus, it provides essentially a way to
extract the lowest order bit.


Best

Kai-Uwe Bux

 

[James Kanze]

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

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]

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]

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.

 

[Andrew Koenig]

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.

 

[Andrew Koenig]

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.

 

[Andrey Tarasevich]

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.

 

[James Kanze]

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