How many bits are '1' in a integer variable?

[Guest]

Richard Heathfield posted:

Your solution doesn't appear to cope with integers wider than 21 bits,
for a start. Secondly, it doesn't cope with integers that are /fewer/
than 21 bits wide! Thirdly, it could conceivably be counting "padding
bits", bits that do not contribute to the value of the integer.

"If the value of the right operand is negative or is greater
than or equal to the width in bits of the promoted left operand, the
behavior is undefined."

I meant something more along the following lines. Do compilers nowadays
optimise away Bitwise-AND operations when one of the operands is known to
be 0 at compile-time?

/* Macro: QUANT_BITS_SET

This macro determines the quantity of bits which
are set in an integer expression whose signedness
is unsigned.

The typedef, "BitsSetType", specifies the unsigned
integer type which is to be used for processing.

Before processing takes place, the argument is
converted to BitsSetType.

This macro should work with unsigned integer types
as wide as 1024 bits.

NB: This macro evaluates its argument more than once.
*/

typedef unsigned BitsSetType;

#define IMAX_BITS(m) (\
(m) /((m)%0x3fffffffL+1) /0x3fffffffL \
%0x3fffffffL *30 \
+ (m)%0x3fffffffL /((m)%31+1)/31%31*5 \
+ 4 \
- 12 / ((m)%31+3) )

#define MASK_ZERO_IF_OVER(shift_left_by) (\
shift_left_by < IMAX_BITS((BitsSetType)-1) \
? (BitsSetType)1 << shift_left_by \
: (BitsSetType)0 )

#define QUANT_BITS_SET_RAW(x) (\
!!((x)&(BitsSetType)1) + !!((x)&(BitsSetType)1<<1) \
+!!((x)&(BitsSetType)1<<2) + !!((x)&(BitsSetType)1<<3) \ ....
+!!((x)&(BitsSetType)1<<14) +!!((x)&(BitsSetType)1<<15) \
+!!((x)&MASK_ZERO_IF_OVER(16))+!!((x)&MASK_ZERO_IF_OVER(17))\ ....
+!!((x)&MASK_ZERO_IF_OVER(1022))+!!((x)&MASK_ZERO_IF_OVER(1023)))

#define QUANT_BITS_SET(x) QUANT_BITS_SET_RAW( ((BitsSetType)(x)) )

#include <stdio.h>

int main(void)
{
/* Let's make an array of length 4 */

int arr[QUANT_BITS_SET(17)];

printf("%u",(unsigned)(sizeof arr/sizeof*arr));
}

The codes prints 2 on my system, but you get the idea...

You know, you could make that a /lot/ shorter, and I know you're so
very fond of IMAX_BITS, but it's unnecessary and without benefits here.
I haven't verified if everything is strictly portable in this version,
but if not, it should serve as at least a starting point.

#define COUNT_8(x) (!!((x) & 0x80)) + (!!((x) & 0x40)) \
+ (!!((x) & 0x20)) + (!!((x) & 0x10)) \
+ (!!((x) & 0x08)) + (!!((x) & 0x04)) \
+ (!!((x) & 0x02)) + (!!((x) & 0x01))
#define COUNT_16(x) COUNT_8 ((x) & 0xFFULL) \
+ COUNT_8 ((x) >> 8)
#define COUNT_32(x) COUNT_16 ((x) & 0xFFFFULL) \
+ COUNT_16 ((x) >> 16)
#define COUNT_64(x) COUNT_32 ((x) & 0xFFFFFFFFULL) \
+ COUNT_32 ((x) >> 32)
#define COUNT_128(x) COUNT_64 ((x) & 0xFFFFFFFFFFFFFFFFULL) \
+ COUNT_64 ((x) >> 60 >> 4)
#define COUNT_256(x) COUNT_128(((1ULL << 60 << 60 << 8) - 1) & (x)) \
+ COUNT_128( (x) >> 60 >> 60 >> 8)
#define COUNT_512(x) COUNT_256(((1ULL << 60 << 60 << 60 << 60 << 16) -
1) & (x)) \
+ COUNT_256( (x) >> 60 >> 60 >> 60 >> 60 >> 16)
#define COUNT_1024(x)COUNT_512(((1ULL << 60 << 60 << 60 << 60 << 60 <<
60 << 60 << 60 << 32) - 1) & (x)) \
+ COUNT_512( (x) >> 60 >> 60 >> 60 >> 60 >> 60#define COUNT(x) COUNT_1024((unsigned long long) x)

You'll need to fix the line wrapping a bit, but it should be obvious
where. (Maybe uintmax_t would be better than unsigned long long.)

 

[mark]

kondal said:



What makes you think this is faster?

Good question. That % 255 looks expensive to me.

And what happens when the code is
ported to a platform with 64-bit unsigned ints?

The code works as expected.

Did you perhaps mean 256?

Mark Williams

 

[mark]

There is no loop here to check and no of clock cycles to be executed
would be fas less than my previous algorithm.

Here is the program for 64 bits

#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
#define MASK_00001111 (((unsigned int)(-1))/17)
#define MASK_00111100 (((unsigned int)(-1))/257)

A very strange name for this last mask... I guess it doesnt matter, but
still...

int bitcount (unsigned int n)
{
n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
n = (n & MASK_00111100) + ((n >> 8) & MASK_00111100) ;
return n % 255 ;
}

Your original code worked for ints up to 255 bits. This version would
work with ints up to 65535 bits if you changed the last line to:

return n % 65535.

Mark Williams

 

[Richard Heathfield]

mark said:

Good question. That % 255 looks expensive to me.


The code works as expected.

Did you perhaps mean 256?

I actually meant n, for arbitrarily large n.

 

[Frederick Gotham]

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:

You know, you could make that a /lot/ shorter, and I know you're so
very fond of IMAX_BITS, but it's unnecessary and without benefits here.
I haven't verified if everything is strictly portable in this version,
but if not, it should serve as at least a starting point.

The whole point of me writing that original code in such a pendantic and
horribly verbose manner is that it would be fully-portable.

I don't see how your code could be used (in the portable sense, that is).

 

[Guest]

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:



The whole point of me writing that original code in such a pendantic and
horribly verbose manner is that it would be fully-portable.

I don't see how your code could be used (in the portable sense, that is).

I haven't verified that it's strictly portable, but if there's anything
not strictly portable in it, it's trivially changed, because the
essence of it is valid. If you have a value of at most 1024 bits, you
can get the most significant bits by right-shifting by 512, and if you
do that in multiple operations, you avoid the restrictions on >>'s
right operand. You can get the 512 least significant bits by finding a
mask of either all bits one if there are no more than 512 bits, or
(2**512 - 1) if there are more. (1ULL << 512) (split into multiple
operations) is either 2**512, or 0, because of the rules for unsigned
overflow. So (1ULL << 512) - 1 is exactly that mask. You can repeat
this process to split both 512-bit values into 256-bit values, and so
on. What do you think is wrong with it?

 

[pete]

mark said:


I actually meant n, for arbitrarily large n.

The comparitive timing is even more complicated than all that.

The running time for the alternate method, which was:
n = 0;
while(x)
{
x &= (x-1)
n++;
}
is proportional to the final value of (n).

It's conceivable that there may be some situations
where the final value of (n) will usually be low,
and other situations
where the final value of (n) will usually be high.

 

[kondal]

The comparitive timing is even more complicated than all that.

The running time for the alternate method, which was:
n = 0;
while(x)
{
x &= (x-1)
n++;
}
is proportional to the final value of (n).

It's conceivable that there may be some situations
where the final value of (n) will usually be low,
and other situations
where the final value of (n) will usually be high.

Yep, the worst case would be when all the bits are set.

-kondal

 

[kondal]

mark said:


I actually meant n, for arbitrarily large n.

I picked the code from somewhere in the net and wrote it in my snippets
notebook during college days. If you had a better code i don't mind
using that and enterring it into my snippets book for reference under
your name.

Do you have the code for arbitrarily large n?

-kondal

 

[kondal]

A very strange name for this last mask... I guess it doesnt matter, but
still...

I really didn't check about the macro naming, I just kept something,
sorry for misleading,

Your original code worked for ints up to 255 bits. This version would
work with ints up to 65535 bits if you changed the last line to:

return n % 65535.

really!!, its a good point I haven't checked that.

-kondal

 

[Samuel Stearley]

Your original code worked for ints up to 255 bits. This version would
work with ints up to 65535 bits if you changed the last line to:

return n % 65535.

Mark Williams

1) I think MASK_00111100 should be MASK_11111111

2) return n % 65535 is expensive !
That should be changed to n & 65535.
OR
n % 65536 and hopefully the compiler will optimize it into n & 65535

 

[Jean-Marc Bourguet]

1) I think MASK_00111100 should be MASK_11111111

2) return n % 65535 is expensive !
That should be changed to n & 65535.
OR
n % 65536 and hopefully the compiler will optimize it into n & 65535

You have missed that n%255 or n%65535 does a sideaway
addition (exactly like in base 10, summing the digits is
doing %9).

Someone did measurements on several variants:
http://www-db.stanford.edu/~manku/bitcount/bitcount.html
As expected, table lookup are on top... but they need the
table to be in cache.

Yours,

 

[Samuel Stearley]

Cool I've learned something new today

You have missed that n%255 or n%65535 does a sideaway
addition (exactly like in base 10, summing the digits is
doing %9).

Someone did measurements on several variants:
http://www-db.stanford.edu/~manku/bitcount/bitcount.html
As expected, table lookup are on top... but they need the
table to be in cache.

Yours,

 

[Richard Heathfield]

kondal said:

Do you have the code for arbitrarily large n?

Did I not already post, in this very thread, code that works for arbitrarily
large n? I could have sworn I did.

 

[Frederick Gotham]

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:

What do you think is wrong with it?

Sorry, I was mistaken, your code is good. I've been playing around with it
for a while, and this is my latest effort. I don't know why, but my PC
freezes when I try to compile it. Nonetheless, here it is, a compile-time
constant specifying the quantity of bits which are set in an unsigned
integer expression.

(Note that I append "RAW" to the name of a macro function to indicate that
it doesn't parenthesize its arguments.)

/* Source file: core.c */

#include "header.hpp"

#include <stdio.h>

unsigned const arr[] =
{1,3,5,7,9,
667,668,669,770,
1022,1023,1024,1025};

int main(void)
{
unsigned const *p = arr,
*const pover = arr + sizeof arr/sizeof*arr;

unsigned register i;

do i = *p++, printf("%u",QUANT_BITS_SET(i));
while(p!=pover);

return 0;
}


/* Header file: header.h */

#define IMAX_BITS_RAW(m) (\
m /(m%0x3fffffffL+1) /0x3fffffffL %0x3fffffffL *30 \
+ m%0x3fffffffL /(m%31+1)/31%31*5 \
+ 4 \
- 12 /(m%31+3) )


/* Macro: MAX_VALUE_FOR_UNSIGNED_TYPE_OF_EXPR_RAW

This macro takes an integer expression, and
yields the highest value for the unsigned integer
type corresponding to the expression (after
integer promotion takes place). */

#define MAX_VALUE_FOR_UNSIGNED_TYPE_OF_EXPR_RAW(expr)\
(expr-expr-1U)


/* Macro: BITS_IN_UNSIGNED_TYPE_OF_EXPR_RAW

This macro takes an integer expression, and
yields the amount of value representation bits
in the unsigned integer type corresponding
to the expression. (after integer promotion
takes place)*/

#define BITS_IN_UNSIGNED_TYPE_OF_EXPR_RAW(expr) \
IMAX_BITS_RAW( \
MAX_VALUE_FOR_UNSIGNED_TYPE_OF_EXPR_RAW(expr) )


/* Macro: RIGHT_SHIFT_NO_REDUNDANT_RAW

This macro provides a "safe" form of
right shifting, whereby the amount of bits
to shift by may be larger than the actual
type (in such cases, it yields zero.)*/

#define RIGHT_SHIFT_NO_REDUNDANT_RAW(x,spaces) (\
BITS_IN_UNSIGNED_TYPE_OF_EXPR_RAW(x) > spaces \
? x >> s \
: x - x )

#define QUANT_BITS_SET_16_RAW(x) (\
!!(x&1U) + !!(x&1U<<1) \
+!!(x&1U<<2) + !!(x&1U<<3) \
+!!(x&1U<<4) + !!(x&1U<<5) \
+!!(x&1U<<6) + !!(x&1U<<7) \
+!!(x&1U<<8) + !!(x&1U<<9) \
+!!(x&1U<<10) +!!(x&1U<<11) \
+!!(x&1U<<12) +!!(x&1U<<13) \
+!!(x&1U<<14) +!!(x&1U<<15) )

#define QUANT_BITS_SET_32_RAW(x)\
QUANT_BITS_SET_16_RAW(x)\
+ QUANT_BITS_SET_16_RAW(RIGHT_SHIFT_NO_REDUNDANT_RAW(x,16))

#define QUANT_BITS_SET_64_RAW(x)\
QUANT_BITS_SET_32_RAW(x)\
+ QUANT_BITS_SET_32_RAW(RIGHT_SHIFT_NO_REDUNDANT_RAW(x,32))

#define QUANT_BITS_SET_128_RAW(x)\
QUANT_BITS_SET_64_RAW(x)\
+ QUANT_BITS_SET_64_RAW(RIGHT_SHIFT_NO_REDUNDANT_RAW(x,64))

#define QUANT_BITS_SET_256_RAW(x)\
QUANT_BITS_SET_128_RAW(x)\
+ QUANT_BITS_SET_128_RAW(RIGHT_SHIFT_NO_REDUNDANT_RAW(x,128))

#define QUANT_BITS_SET_512_RAW(x)\
QUANT_BITS_SET_256_RAW(x)\
+ QUANT_BITS_SET_256_RAW(RIGHT_SHIFT_NO_REDUNDANT_RAW(x,256))

#define QUANT_BITS_SET_1024_RAW(x)\
QUANT_BITS_SET_512_RAW(x)\
+ QUANT_BITS_SET_512_RAW(RIGHT_SHIFT_NO_REDUNDANT_RAW(x,512))

#define QUANT_BITS_SET(x)\
(QUANT_BITS_SET_1024_RAW((x)))