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?

 
 
tfeldman21@gmail.com
Guest
Posts: n/a
 
      02-16-2007
On 32-bit platform,
I am working on getting how many bits equal to 1 without an if loop.

--
Regards.
Terrence Feldman
Email: http://www.velocityreviews.com/forums/(E-Mail Removed)

 
Reply With Quote
 
 
 
 
=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
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.


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.

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


Your task is made easier by the fact that there's no such thing as an
"if loop", so you won't have any trouble avoiding it.

The most important step in solving any problem is defining exactly
what the problem is. You haven't done that.

But questions of the form "How can I do X without using feature Y?"
are almost always homework assignments. We won't do your homework for
you (unless you're willing to pay our exhorbitant consulting fees
*and* let us submit our solutions directly to your instructor).

We're quite willing to help you solve any problems in your C code, but
we can't do that unless you write some and post it.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      02-16-2007
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.

--
<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
 
Malcolm McLean
Guest
Posts: n/a
 
      02-16-2007

<(E-Mail Removed)> wrote in message n
> On 32-bit platform,
> I am working on getting how many bits equal to 1 without an if loop.
>

On the lowest bit can equal one. The rest equal 2, 4, 8 ... etc.

So if (x & 1) is your answer.

Tell your professor he means the number of set bits.


 
Reply With Quote
 
=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a
 
      02-16-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.
> [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.

 
Reply With Quote
 
=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a
 
      02-16-2007
Harald van Dijk 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;


count = 0;

> for (bit = 1; bit < INT_MAX / 2; bit *= 2)


for (bit = 1; bit != 0; bit *= 2)

> if (value & bit)
> count++;
>
> It accepts ints of any width.


The question asked for unsigned ints, but I posted an example for ints.

 
Reply With Quote
 
=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a
 
      02-16-2007
Harald van Dijk wrote:
> Harald van Dijk 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;

>
> count = 0;
>
> > for (bit = 1; bit < INT_MAX / 2; bit *= 2)

>
> for (bit = 1; bit != 0; bit *= 2)
>
> > if (value & bit)
> > count++;
> >
> > It accepts ints of any width.

>
> The question asked for unsigned ints, but I posted an example for ints.


Sorry for replying to myself so much, but the example for ints was
wrong anyway. After the loop exited, I needed to check value & bit
once more, to see if the highest value bit was set.

 
Reply With Quote
 
Ksitami
Guest
Posts: n/a
 
      02-16-2007
static inline ulong bit_count(ulong x) {
// Return number of bits set
x = (0x55555555 & x) + (0x55555555 & (x>> 1)); // 0-2 in 2 bits
x = (0x33333333 & x) + (0x33333333 & (x>> 2)); // 0-4 in 4 bits
x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x>> 4)); // 0-8 in 8 bits
x = (0x00ff00ff & x) + (0x00ff00ff & (x>> ); // 0-16 in 16
bits
x = (0x0000ffff & x) + (0x0000ffff & (x>>16)); // 0-31 in 32
bits
return x;
}

//Algorithms for programmers ideas and source code
//by Jorg Arndt, (E-Mail Removed)

 
Reply With Quote
 
CoL
Guest
Posts: n/a
 
      02-16-2007
You also try recursion for the same....

~col

On Feb 16, 3:03*pm, "Harald van Dijk" <(E-Mail Removed)> 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.



 
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