Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > How to count bits in a unsigned int?

Reply
Thread Tools

How to count bits in a unsigned int?

 
 
Christopher Layne
Guest
Posts: n/a
 
      02-16-2007
CoL wrote:

> You also try recursion for the same....
>
> ~col


To count bits? You're not in the business of performance eh?
 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      02-16-2007
Harald van D?k wrote:
>
> CBFalconer wrote:
> > Harald van D?k wrote:
> > > http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> > >
> > >> On 32-bit platform, I am working on getting how many bits equal
> > >> to 1 without an if loop.
> > >
> > > Use a for loop or a while loop, testing each bit until you have
> > > no more bits to test. I'm not sure what an if loop would be like,
> > > unless you're using goto.

> >
> > I have no idea what an 'if loop' is.
> > [example]
> > which doesn't care how wide an int is.

>
> And the way I mentioned does?
>
> count = value < 0;
> for (bit = 1; bit < INT_MAX / 2; bit *= 2)
> if (value & bit)
> count++;
>
> It accepts ints of any width.


But it needs to know the precise type. My version will work when
fed bytes, longs, shorts, etc. (with matching changes in the type
of value, but making value an unsigned long will cover them all,
except long long which may or may not be available).

I find code fragments that need no editing more useful.
--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews


 
Reply With Quote
 
 
 
 
Christopher Layne
Guest
Posts: n/a
 
      02-16-2007
CBFalconer wrote:

> But it needs to know the precise type. My version will work when
> fed bytes, longs, shorts, etc. (with matching changes in the type
> of value, but making value an unsigned long will cover them all,
> except long long which may or may not be available).
>
> I find code fragments that need no editing more useful.


What's wrong with the typical straightforward way?

int bs(unsigned long v)
{
int c;

for (c = 0; v; v >>= 1)
c += v & 1;

return c;
}
 
Reply With Quote
 
=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a
 
      02-16-2007
CBFalconer wrote:
> Harald van D?k wrote:
> >
> > CBFalconer wrote:
> > > Harald van D?k wrote:
> > > > (E-Mail Removed) wrote:
> > > >
> > > >> On 32-bit platform, I am working on getting how many bits equal
> > > >> to 1 without an if loop.
> > > >
> > > > Use a for loop or a while loop, testing each bit until you have
> > > > no more bits to test. I'm not sure what an if loop would be like,
> > > > unless you're using goto.
> > >
> > > I have no idea what an 'if loop' is.
> > > [example]
> > > which doesn't care how wide an int is.

> >
> > And the way I mentioned does?
> >
> > count = value < 0;
> > for (bit = 1; bit < INT_MAX / 2; bit *= 2)
> > if (value & bit)
> > count++;
> >
> > It accepts ints of any width.

>
> But it needs to know the precise type. My version will work when
> fed bytes, longs, shorts, etc. (with matching changes in the type
> of value, but making value an unsigned long will cover them all,
> except long long which may or may not be available).
>
> I find code fragments that need no editing more useful.


Your version will not work with signed types, and the version for
unsigned types I posted later does not need editing either, as long as
the type of 'bit' is large enough.

 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      02-16-2007
Christopher Layne wrote:
> CBFalconer wrote:
>
>> But it needs to know the precise type. My version will work when
>> fed bytes, longs, shorts, etc. (with matching changes in the type
>> of value, but making value an unsigned long will cover them all,
>> except long long which may or may not be available).
>>
>> I find code fragments that need no editing more useful.

>
> What's wrong with the typical straightforward way?
>
> int bs(unsigned long v)
> {
> int c;
>
> for (c = 0; v; v >>= 1)
> c += v & 1;
> return c;
> }


Nothing that I can see. It will take more cycles, for each 0 bit
to the right of any 1 bit.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews


 
Reply With Quote
 
Radamanthe
Guest
Posts: n/a
 
 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      02-16-2007
(E-Mail Removed) wrote:
>
> On 32-bit platform,
> I am working on getting how many bits equal to 1 without an if loop.


unsigned bit_count(unsigned n)
{
unsigned count;

for (count = 0; n != 0; n &= n - 1) {
++count;
}
return count;
}

--
pete
 
Reply With Quote
 
jxh
Guest
Posts: n/a
 
      02-16-2007
On Feb 16, 5:01 am, Christopher Layne <(E-Mail Removed)> wrote:
> CoL wrote:
> > You also try recursion for the same....

>
> > ~col

>
> To count bits? You're not in the business of performance eh?


Should perform just as well with proper optimizations:

static int
bits_r (unsigned int u, int count)
{
return !u ? count : bits_r(u & u-1, count+1);
}

int
bits (unsigned int u)
{
return bits_r(u, 0);
}

-- James

 
Reply With Quote
 
dick
Guest
Posts: n/a
 
      02-17-2007

CBFalconer wrote:
> Harald van D?k wrote:
> > (E-Mail Removed) wrote:
> >
> >> On 32-bit platform, I am working on getting how many bits equal
> >> to 1 without an if loop.

> >
> > Use a for loop or a while loop, testing each bit until you have
> > no more bits to test. I'm not sure what an if loop would be like,
> > unless you're using goto.

>
> I have no idea what an 'if loop' is.
>
> unsigned int value, count;
>
> value = whatever;
> count = 0;
>
> /* loop invariant: count + bitsinvalue = bitsinwhatever */
> while (value) {
> count++;
> value = (value - 1) & value;
> }
> /* bitsinvalue = 0 */
>
> which doesn't care how wide an int is.


this is an interview question.

i = 0;
while(var)
{
var &= ~(-var);
i++;
}

 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      02-17-2007
dick wrote:
> CBFalconer wrote:
>> Harald van D?k wrote:
>>> (E-Mail Removed) wrote:
>>>
>>>> On 32-bit platform, I am working on getting how many bits equal
>>>> to 1 without an if loop.
>>>
>>> Use a for loop or a while loop, testing each bit until you have
>>> no more bits to test. I'm not sure what an if loop would be like,
>>> unless you're using goto.

>>
>> I have no idea what an 'if loop' is.
>>
>> unsigned int value, count;
>>
>> value = whatever;
>> count = 0;
>>
>> /* loop invariant: count + bitsinvalue = bitsinwhatever */
>> while (value) {
>> count++;
>> value = (value - 1) & value;
>> }
>> /* bitsinvalue = 0 */
>>
>> which doesn't care how wide an int is.

>
> this is an interview question.
>
> i = 0;
> while(var)
> {
> var &= ~(-var);
> i++;
> }


Doesn't work. Consider overflow (-var, for var == INT_MIN, 2'
complement), sign-magnitude representation, 1's complement
representation.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
(int) -> (unsigned) -> (int) or (unsigned) -> (int) -> (unsigned):I'll loose something? pozz C Programming 12 03-20-2011 11:32 PM
what about unsigned and signed 8 bits number, 16 bits, etc?? sarmin kho Python 2 06-15-2004 06:40 PM
Re: what about unsigned and signed 8 bits number, 16 bits, etc?? Miki Tebeka Python 1 06-14-2004 03:19 PM
8-Bits vs 12 or 16 bits/pixel; When does more than 8 bits count ? Al Dykes Digital Photography 3 12-29-2003 07:08 PM



Advertisments