Timeline for Counting the number of "on" bits in an int
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2016 at 3:13 | comment | added | phuclv | Then you can simply shift to the left. Anyway the recommended solution is using a table lookup or parallel counting. Those are much faster than this simple way | |
| Nov 7, 2016 at 3:09 | comment | added | ad absurdum |
@Lưu Vĩnh Phúc -- I don't claim that this is the naive way. This is based on Kernighan's method from your link. This way works for 2's complement, and I believe also for 1's complement. But this naive method failed on my system, for negative values of v, due to bit-shifting a negative value to the right. The loop never terminates, I believe because v never reaches 0.
|
|
| Nov 7, 2016 at 3:02 | comment | added | phuclv | This is not the naive way. The naive way works with any signed format, regardless of logical or arithmetic shift because the final result is always and with 1. This way implies 2's complement | |
| Nov 7, 2016 at 2:22 | comment | added | ad absurdum |
Maybe I should change to: int sb = 0x1; sb <<= (CHAR_BIT * sizeof(int) - 1); sb = ~sb;? Do I need to do this to guarantee that 0x1 can always be bit-shifted by the required amount?
|
|
| Nov 7, 2016 at 2:09 | comment | added | ad absurdum | @Edward-- the standard guarantees 2's, 1's, or sign-magnitude representation (c99 6.2.6.2/2). For this solution, I only claim that it will work for both 2's and 1's complement. (6.5.3.4/4) guarantees that the result of sizeof is an unsigned integer type. If I am reading (5.2.4.2/1) correctly, CHAR_BIT must be positive and at least 8, so this expression must be non-negative. If I am missing something here, I really want to understand it. I would also love to see an alternative, if you get a chance. Thank you for the attention. | |
| Nov 7, 2016 at 1:50 | comment | added | Edward | It's exceedingly likely that everything will work out (e.g. no numeric overflow from the multiplication) and that every real implementation uses two's-complement, but I don't believe it's guaranteed by my reading of the standard. If I had more time to look into it, I'd provide an alternative answer. Perhaps I will if I get some time this week. | |
| Nov 7, 2016 at 1:50 | comment | added | Edward |
The standard says, of the left bitshift operator, that "If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined." The additive-expression CHAR_BIT * sizeof(int) - 1does not necessarily assure that because both CHAR_BIT and sizeof(int) (and for that matter, - 1) are all implementation defined.
|
|
| Nov 7, 2016 at 1:24 | history | edited | Jamal | CC BY-SA 3.0 |
deleted 10 characters in body
|
| Nov 7, 2016 at 1:16 | history | edited | ad absurdum | CC BY-SA 3.0 |
deleted 8 characters in body
|
| Nov 6, 2016 at 23:49 | history | edited | ad absurdum | CC BY-SA 3.0 |
added 2 characters in body
|
| Nov 6, 2016 at 22:13 | comment | added | ad absurdum | @Edward-- Thank you for your observations. This is exactly why I put this here. I was under the impression that the additive-expression of a bitwise shift operator was only required to be non-negative, which the above expression satisfies. I don't see how this is a problem here. What am I missing? | |
| Nov 6, 2016 at 22:05 | comment | added | Edward |
To the latter point, this proposed code has a similar issue because both CHAR_BIT and the result of the sizeof operator could either be signed or unsigned. This is a good illustration of the previous point which is that the same code might "work" on different implementations or it might not. It also might produce the same number given the same input, or it might not. This is the very definition of non-portable code, but the fault is not in your implementation -- it's inherent to the problem.
|
|
| Nov 6, 2016 at 21:56 | comment | added | ad absurdum | @Edward-- that said, I have reservations about my use of both unsigned and int in the same expression in my original code, and the effects of padding bits in this situation are unclear to me, as I don't have a good handle on exactly how padding bits work in integer representations. | |
| Nov 6, 2016 at 21:54 | comment | added | ad absurdum | @Edward-- I am not sure that I get your meaning. If you are saying that an implementation that uses two's complement will produce different results than one that uses one's complement, then yes, of course. But it would be nice if the same code worked on both implementations. The solution in my original question works for all three of the representations allowed by the standard. The solution in this answer works for two of the three representations. The bit-counts will differ, but the code will still work. | |
| Nov 6, 2016 at 21:47 | comment | added | Edward |
By definition, any function that counts set bits will be implementation specific because the implementation details of the int type are implementation specific.
|
|
| Nov 6, 2016 at 18:48 | history | answered | ad absurdum | CC BY-SA 3.0 |