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

This is a discussion on How many bits are '1' in an integer variable? within the C Programming forums, part of the General Programming Boards category; Originally Posted by cuthbert The fastest way I found is using lookup table. For integer, 4 bytes long, it takes ...

  1. #31
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by cuthbert
    The fastest way I found is using lookup table. For integer, 4 bytes long, it takes 4 additional operators only.
    I am not 100% sure what you mean by that, did you look at the object code and count the instructions?
    The actually run time is probably not directly related to the number of instruction, although it is a
    good guide. Some instructions take longer to execute than others, depending on various factors. The best way to determine the actually would be to time a test run of several thousands runs of the programs code? I might try that for a laugh - I'm bored!!

  2. #32
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Some compilers allow you to view the assembly output.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #33
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by citizen
    > You could but it would take 8 times longer to complete (at least).
    Performance isn't always a problem, and this is beyond the scope of the original question.
    The OP said:-
    "I am trying to find a more efficient way to count "How many bits are'1' in an integer variable?"."

    So it depends what he means by efficient, if he means efficient in run time then it is in scope, in my opinion. He didn't specify exactly what he meant but he did mention opcode (IIRC) which could mean the number of opcodes in the program or the number executed, again he didn't
    specify.

  4. #34
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    Except that you also said the following:
    I guess the fastest way would be really huge look up table, for a 32 bit int you would need
    4 gigabites+ of memory though.
    For a 64 bit int well, you might need a loan to buy the memory
    This thread wasn't even about integers that huge until you brought it up. But by all means, lets ignore an entire data structure because you think it doesn't work.

    The program might take a while to load but once loaded it would run like lightening!!
    Here you refute your own argument because many programs take a while to load and then run smoothly. That's exactly what the op wants. Computers happen to be fast at math most of the time so it's time that probably won't be missed.

  5. #35
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Funny, Cuthbert asked this same question in comp.lang.c. Pete as usual posted a nice solution.

  6. #36
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,475
    I still proclaim itoa() the fastest... non portable way
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  7. #37
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Fastest how? In developement time, because you don't have to type anything?
    There's no way it's going to beat a lookup table, even if you do have to do it a byte at a time.


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #38
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,475
    hmm... yes. You are right. I was only looking at the problem isolated from its possible uses, not thinking it could be called inumerous times. A lookup table would be a burden in that case.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  9. #39
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    > for ( i = 0; i < sizeof(int)*8 ; i++ )
    Use the value of CHAR_BIT, not 8
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #40
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    324
    Quote Originally Posted by Mario F.
    A non-portable way is to use itoa() if your compiler supports it, with a radix of 2. This will return a C-style string you can then count for 1s.

    A portable way involves the use of recursion as seen here http://www.engin.umd.umich.edu/CIS/c...pp/binary.html, changing it where appropriate to count 1s.

    Both options are faster than what you are doing.

    EDIT: Well... swoopy's faster no doubt
    I see a call to integer division in that code, are you saying that integer division (the mod operator) is faster than a shift and a bitwise AND like the OP's code ?

    I don't see how the recursive one would be any faster, anyone care to test it?

  11. #41
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,475
    Did you look closely at it?

    You don't have to iterate sizeof(int)*8 times to output the result unless your int is that big.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  12. #42
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    324
    I know of a way to do it in ASM that only iterates 1 time for each bit in the integer but I don't know if it can be done in C aside from using inline assembly; it involves the use of the ROL (or ROR) operation plus the JC operation.

  13. #43
    Fountain of knowledge.
    Join Date
    May 2006
    Posts
    794
    Quote Originally Posted by MacNilly
    I know of a way to do it in ASM that only iterates 1 time for each bit in the integer but I don't know if it can be done in C aside from using inline assembly; it involves the use of the ROL (or ROR) operation plus the JC operation.

    The C >> and << commands are the equivilant of ROR and ROL

  14. #44
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,164
    Quote Originally Posted by esbo
    The C >> and << commands are the equivilant of ROR and ROL
    No. The << and >> operators are more equivalent to SHL and SHR. The difference being ROR and ROL slap the shifted-off bit back on the other end, kind of like a conveyer belt.

    I wish you'd stop spreading bad information. If you don't know the answer, don't make it seem like you do.
    Last edited by itsme86; 09-13-2006 at 11:57 AM.
    If you understand what you're doing, you're not learning anything.

  15. #45
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    > The C >> and << commands are the equivilant of ROR and ROL
    No they are not.
    ROL would (in 8 bits) turn 0x80 into 0x01, where the C operator would turn it into 0
    << and >> propagate zeros (mostly), not the bits which fall off the end.

    ASL and ASR or SAL and SAR are more likely choices.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Page 3 of 4 FirstFirst 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-20-2009, 11:37 PM
  2. Need some help...
    By darkconvoy in forum C Programming
    Replies: 32
    Last Post: 04-29-2008, 03:33 PM
  3. Replies: 7
    Last Post: 08-19-2007, 08:10 AM
  4. load gif into program
    By willc0de4food in forum Windows Programming
    Replies: 14
    Last Post: 01-11-2006, 09:43 AM
  5. Im so lost at . .
    By hermit in forum C Programming
    Replies: 18
    Last Post: 05-15-2002, 01:26 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21