function to count number of set bits

[Eric Sosman]

[...] There is
no such thing as a negative constant, only a constant to which
you apply a negating unary operator.

Three pettifogging counter-examples (two implementation-
specific):

enum { NEGATIVE = -42, POSITIVE = 42 };
/* Henceforth, `NEGATIVE' is a negative constant. */

'\x99'
/* A constant whose value may be negative on some
* implementations, depending on the value of CHAR_BIT
* and the signedness of `char'.
*/

'ß'
/* A constant whose value may be negative on some
* implementations (and which might be utterly rejected
* by some others, since the character is not in the set
* mandated by the Standard).
*/

 

[Ben Pfaff]

[...] There is
no such thing as a negative constant, only a constant to which
you apply a negating unary operator.

Three pettifogging counter-examples (two implementation-
specific):

Okay, let me try again. There is no such thing as a negative
integer-constant or floating-constant, but you may apply a
negating unary operator to obtain a negative value.

Anybody want to dispute *that*?

 

[Chris Torek]

And if the implementation-defined value happens to be -32768, the
implementation is free to use it as the definition of INT_MIN. (There
are good reasons not to do so. Keeping <limits.h> in sync with the
compiler might be non-trivial, and you might as well have a portable
definition of INT_MIN if you can.)

There is another good reason not to use a cast here. Suppose
INT_MIN is in fact -32768 (numerically), and the implementation
uses a cast in the "#define" for INT_MIN. Then consider:

#if INT_MIN < (-2147483647 - 1)
/* int is at least 32 bits */
...
#endif

When the compiler sees this during the preprocessing phase in which
keywords have no meaning (because there are only pp-tokens, not
yet any tokens), we get:

#if ((some_pp_token)-32768) < (-2147483647 - 1)

which is syntactically invalid and requires a diagnostic. My C99
draft says, in part:

[#1] The values given below shall be replaced by constant
expressions suitable for use in #if preprocessing
directives.

(C89 has similar if not identical wording.)

 

[Eric Sosman]

CBFalconer wrote:

Look at the way INT_MIN is usually defined [...]

Note that `(int)-32768' wouldn't work, since the value
must be a constant expression and constant expressions can't
contain cast operators.

Casts are allowed in constant expressions although there are some
restrictions which don't apply here. The problem with (int)-32768 where
INT_MAX is 32767 and UINT_MAX is 65535 is that it is equivalent to
(int)(32768U) i.e. you are trying to convert to a signed integer type a
value that is not representable in that type. That's undefined in C90 and
in C99 you get an implementation-defined value or signal.

Sorry; sloppy language on my part. Casts are indeed
permitted in "constant expressions" (6.6), but they are
forbidden in the special form of "constant expression" the
preprocessor can evaluate (6.10.1). INT_MIN and friends
must be evaluable by the preprocessor (5.2.4.2.1), and so
cannot be defined with casts.

 

[Big K]

Hi, I'm wondering if anyone knows if the following function will
function properly as a set-bit counter on non 2s complement machines
(as K&R2 implies).

| int bitcount(unsigned x)
| {
| int count;
|
| for(count = 0; x != 0; count++, x &= (x-1))
| ;
|
| return count;
| }

I can't think of a reason why this would fail on a 1s complement or
sign-mag machine (and can't find a non 2s compliment machine to try it
on). Is it portable as far as C is concerned?

If the intention is to call the function from either signed or unsigned
int, then the code will not work on non-2s complement machiens for
signed ints.

Say for example you have -0 on a sign-mag or 1s comp. machine in an int
variable y:

Even though the y is not devoid of set bits on those machines, once the
call is made to the function and the variable is converted from signed
-> unsigned, C's rules will whipe out all the set bits (via -0 +
UINT_MAX + 1). Your function will return 0 as the # of set bits
because of the conversion that took place on the argument before
function entry. This is an example of C's bias towards 2's complement
machines (which is understandable because 2's complement is the "best"
way to represent negative integers!).

So the authors of K&R were probably warning you about calling the
function with signed ints (not portable).

 

[Chris Torek]

[Given a bit-counting function that takes an unsigned int or unsigned
long parameter...]

If the intention is to call the function from either signed or unsigned
int, then the code will not work on non-2s complement machiens for
signed ints.

Well, that depends on what one *wants*.

Say for example you have -0 on a sign-mag or 1s comp. machine in an int
variable y:

Even though the y is not devoid of set bits on those machines, once the
call is made to the function and the variable is converted from signed
-> unsigned, C's rules will whipe out all the set bits (via -0 +
UINT_MAX + 1). Your function will return 0 as the # of set bits
because of the conversion that took place on the argument before
function entry.

Indeed it will. And yet, on such a machine, if -0 is produced by
ordinary arithmetic (as opposed to being used to detect uninitialized
variables, for instance), C requires that x==y be true even if x
is -0 and y is +0. That is:

x = <expression 1>;
y = <expression 2>;
if (x == y && bitcount(x) != bitcount(y))
puts("how peculiar!");

should never print the message, even if x is -0 and y is +0. So
you might *want* bitcount() to return 0 in both cases.

On the other hand, if you want to inspect the representation,
rather than the value, of a variable, you can still write that:

int representational_bit_count(unsigned char *p, int size);
#define RBC(var) \
representational_bit_count((unsigned char *)&(var), sizeof(var))
...
if (x == y && RBC(x) != RBC(y))
puts("while x==y, their representations differ");

Note, however, that two identical and nonnegative values can still
have differing representations, if some of the bits in the
representations are padding bits.

This is an example of C's bias towards 2's complement
machines (which is understandable because 2's complement is the "best"
way to represent negative integers!).

While *I* am biased towards 2'sC I am not so sure C really is.
C gives you the ability to inspect representations (via pointers
and "unsigned char *"); it is up to you, the programmer, not to
abuse it.

 

[Luke Wu]

Hi, I'm wondering if anyone knows if the following function will
function properly as a set-bit counter on non 2s complement machines
(as K&R2 implies).

K&R2 was implying that the expression x &= (x-1) does not remove the
rightmost set bit on all implementations - negative 'even' integers in
sign-mag form will be left unchanged by x &= (x-1)

| int bitcount(unsigned x)
| {
| int count;
|
| for(count = 0; x != 0; count++, x &= (x-1))
| ;
|
| return count;
| }

I can't think of a reason why this would fail on a 1s complement or
sign-mag machine (and can't find a non 2s compliment machine to try it
on). Is it portable as far as C is concerned?

The function itself is portable, because unsigned numbers have no
issues.

 

[G Patel]

[Given a bit-counting function that takes an unsigned int or unsigned
long parameter...]

If the intention is to call the function from either signed or unsigned
int, then the code will not work on non-2s complement machiens for
signed ints.

Well, that depends on what one *wants*.

Say for example you have -0 on a sign-mag or 1s comp. machine in an int
variable y:

Even though the y is not devoid of set bits on those machines, once the
call is made to the function and the variable is converted from signed
-> unsigned, C's rules will whipe out all the set bits (via -0 +
UINT_MAX + 1). Your function will return 0 as the # of set bits
because of the conversion that took place on the argument before
function entry.

Indeed it will. And yet, on such a machine, if -0 is produced by
ordinary arithmetic (as opposed to being used to detect uninitialized
variables, for instance), C requires that x==y be true even if x
is -0 and y is +0. That is:

x = <expression 1>;
y = <expression 2>;
if (x == y && bitcount(x) != bitcount(y))
puts("how peculiar!");

should never print the message, even if x is -0 and y is +0. So
you might *want* bitcount() to return 0 in both cases.

On the other hand, if you want to inspect the representation,
rather than the value, of a variable, you can still write that:

int representational_bit_count(unsigned char *p, int size);
#define RBC(var) \
representational_bit_count((unsigned char *)&(var), sizeof(var))

So what is truly the universal way of counting the respresentational
bits on any platform? I see that you (Chris) use a char pointer
somehow to cycle through the bytes, but will this catch all the extra
bits used for handling overflow detection etc?

...
if (x == y && RBC(x) != RBC(y))
puts("while x==y, their representations differ");

Note, however, that two identical and nonnegative values can still
have differing representations, if some of the bits in the
representations are padding bits.


While *I* am biased towards 2'sC I am not so sure C really is.
C gives you the ability to inspect representations (via pointers
and "unsigned char *"); it is up to you, the programmer, not to
abuse it.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to

spammers.

Anyone know a truly universal function for counting all the setbits in
a signed or unsigned number? I presume the receiving function would
have to accept the parameter into a large signed integer (signed long
long ?).

 

[Luke Wu]

So what is truly the universal way of counting the respresentational
bits on any platform? I see that you (Chris) use a char pointer
somehow to cycle through the bytes, but will this catch all the extra
bits used for handling overflow detection etc?

I think Chris was thinking along the lines of the following
function(which will spit out the C abstract machine level bits (in each
byte) for any object sent to it):


..#include <stdio.h>
..#include <limits.h>
..
..#define RBC(var) repbitcount((unsigned char *)&var, sizeof(var))
..
..int repbitcount(unsigned char *p, int size)
..{
.. int count = 0;
.. int byte;
.. while(size)
.. {
.. byte = CHAR_BIT - 1;
.. while(byte >= 0)
.. {
.. if(*p & 1 << byte)
.. {
.. putchar('1'); /* remove putchar if necessary */
.. count++;
.. }
.. else putchar('0'); /* remove putchar if necessary */
..
.. byte--;
.. }
.. putchar('\n'); /* remove putchar if necessary */
.. size--;
.. p++;
.. }
..}

spammers.

Anyone know a truly universal function for counting all the setbits in
a signed or unsigned number? I presume the receiving function would
have to accept the parameter into a large signed integer (signed long
long ?).

Any bits in a representation not part of C's abstract machine model
(like the the extra bits to detect overflow on some implementations),
can not be portable accessed by a function (to answer your earlier
question).

 

[Kobu]

I think Chris was thinking along the lines of the following
function(which will spit out the C abstract machine level bits (in each
byte) for any object sent to it):


.#include <stdio.h>
.#include <limits.h>
.
.#define RBC(var) repbitcount((unsigned char *)&var, sizeof(var))
.
.int repbitcount(unsigned char *p, int size)
.{
. int count = 0;
. int byte;
. while(size)
. {
. byte = CHAR_BIT - 1;
. while(byte >= 0)
. {
. if(*p & 1 << byte)
. {
. putchar('1'); /* remove putchar if necessary */
. count++;
. }
. else putchar('0'); /* remove putchar if necessary */
.
. byte--;
. }
. putchar('\n'); /* remove putchar if necessary */
. size--;
. p++;
. }
.}

You forgot to return count.