🔒 Locked

bitwise operations in c

Started by samps005 Oct 10, 2002 at 3:41 PM 10 replies 1.9k views

Original Post

Oct 10, 2002 at 3:41 PM

I''m trying to write a program called bitCount - It returns the of number of 1''s in word (32 bit word size) Examples: bitCount(5) = 2, bitCount(7) = 3 Legal ops: ! ~ & ^ | + << >> Max ops: 40 Does anyone think they can do this, or maybe even have some hints

twanvl

Oct 10, 2002 at 3:46 PM

1. Don''t ask people if they will do your homework for you!
2. Hint: Use a for loop, and check for each bit is it''s set

samps005

Author

samps005

Oct 10, 2002 at 4:34 PM

I wasn''t asking anyone to do this for me, I was just wondering if anyone had any ideas as to a good way to go about it.

the tricky part about this is that it needs to be done with out the use of "for" or "while" or "if" or "do while"
just bitwise operatiors like & | << >> ! ^ ~

daerid

Oct 10, 2002 at 5:01 PM

quote:
Original post by samps005

I''m trying to write a program called bitCount -
It returns the of number of 1''s in word (32 bit word size)
Examples: bitCount(5) = 2, bitCount(7) = 3
Legal ops: ! ~ & ^ | + << >>
Max ops: 40

Does anyone think they can do this, or maybe even have some hints

  
#include <stdio.h>
void main(int argc,char** argv)
{
	int num;
	int bitcount = 0;
	
	printf("Enter a number: ");
	scanf("%i",#);
	
	bitcount += ((num & 0x00000001) >> 0);
	bitcount += ((num & 0x00000002) >> 1);
	bitcount += ((num & 0x00000004) >> 2);
	bitcount += ((num & 0x00000008) >> 3);
	bitcount += ((num & 0x00000010) >> 4);
	bitcount += ((num & 0x00000020) >> 5);
	bitcount += ((num & 0x00000040) >> 6);
	bitcount += ((num & 0x00000080) >> 7);
	bitcount += ((num & 0x00000100) >> 8);
	bitcount += ((num & 0x00000200) >> 9);
	bitcount += ((num & 0x00000400) >> 10);
	bitcount += ((num & 0x00000800) >> 11);
	bitcount += ((num & 0x00001000) >> 12);
	bitcount += ((num & 0x00002000) >> 13);
	bitcount += ((num & 0x00004000) >> 14);
	bitcount += ((num & 0x00008000) >> 15);
	bitcount += ((num & 0x00010000) >> 16);
	bitcount += ((num & 0x00020000) >> 17);
	bitcount += ((num & 0x00040000) >> 18);
	bitcount += ((num & 0x00080000) >> 19);
	bitcount += ((num & 0x00100000) >> 20);
	bitcount += ((num & 0x00200000) >> 21);
	bitcount += ((num & 0x00400000) >> 22);
	bitcount += ((num & 0x00800000) >> 23);
	bitcount += ((num & 0x01000000) >> 24);
	bitcount += ((num & 0x02000000) >> 25);
	bitcount += ((num & 0x04000000) >> 26);
	bitcount += ((num & 0x08000000) >> 27);
	bitcount += ((num & 0x10000000) >> 28);
	bitcount += ((num & 0x20000000) >> 29);
	bitcount += ((num & 0x40000000) >> 30);
	bitcount += ((num & 0x80000000) >> 31);
	
	printf("bitcount: %i\n",bitcount);
}

I was feeling nice

botman

Oct 10, 2002 at 5:25 PM

That''s more than 40 operations.

botman

Matt Calabrese

Oct 10, 2002 at 5:35 PM

Just loop through from 0 to 31 for each bit. The big group of lines can be turned into a for statement with 1 line.

Neosmyle

Oct 10, 2002 at 6:01 PM

quote:
Original post by samps005
It returns the of number of 1''s in word (32 bit word size)

Words are typically 16 bit. Are you sure we are talking about a 32-bit variable?

daerid

Oct 10, 2002 at 6:02 PM

quote:
Original post by botman
That''s more than 40 operations.

botman

Herm.. it''s only 33 statements, tho :o

Are you saying you can only use up to 40 operators? And no control structures?

How gay is that...

samps005

Author

samps005

Oct 10, 2002 at 6:11 PM

yeah it''s gay alright,
anyway here is how you do it

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

int bitCount(int x) {
{
x = ( x & 0x55555555 ) + ( ( x >> 1 ) & 0x55555555 );
x = ( x & 0x33333333 ) + ( ( x >> 2 ) & 0x33333333 );
x = ( x & 0x0F0F0F0F ) + ( ( x >> 4 ) & 0x0F0F0F0F );
x = ( x & 0x00FF00FF ) + ( ( x >> 8 ) & 0x00FF00FF );
x = ( x & 0x0000FFFF ) + ( ( x >> 16 ) & 0x0000FFFF );

return x;
}

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

Stoffel

Oct 10, 2002 at 6:43 PM

Looks a lot like optimal byte-reversal too. That''s just spooky.

Zipster

511

Zipster

Oct 10, 2002 at 7:35 PM

I''m glad the original poster didn''t learn anything because we just bombarded him with completed code. Good job guys.

Stoffel

Oct 10, 2002 at 9:59 PM

The OP posted the answer, which (assuming he was a student) most students learning C wouldn''t have been able to come up with on their own. Lighten up.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.