2 ms·
Most architectures seem to have an instruction for finding the leftmost set bit in a word [1] and most major C/C++ compilers/libraries have a function for it [2
by tzs 5y ago
Most architectures seem to have an instruction for finding the leftmost set bit in a word [1] and most major C/C++ compilers/libraries have a function for it [2].
I wonder how using that would compare?
You'd find the leftmost bit, invoke the func_true for that, and clear the leftmost bit.
Then loop finding the leftmost bit, invoking the func_false for the bits between the current leftmost bit and the previous leftmost bit, func_true for the leftmost bit, and then clear that bit.
I wouldn't expect it to be dramatically different, but it is trading test and clear on the off bits and a conditional branch off of the result for a loop calling func_false a predetermined number of times. One of those options might be a little faster than the other.
[1] https://en.wikipedia.org/wiki/Find_first_set#Hardware_support https://en.wikipedia.org/wiki/Find_first_set#Hardware_suppor...
[2] https://en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support https://en.wikipedia.org/wiki/Find_first_set#Tool_and_librar...
- joezydeco 5y agoBack in the 8-bit days you could roll or shift left and the MSB would move to the carry bit or flag. Then branching was built into instructions like BCS/BCC (branch on carry set or clear).
- josephcsible 5y agoBack in the 8-bit days? Isn't that what RCL still does on modern processors?
- joezydeco 5y agoIt probably does for all I know, I just don't do a lot of assembly anymore.
- wmu 5y agoAuthor here. I cannot use BSR, because have to execute code for all bits, regardless their value. The range is: the last bit to the first with value 1. It's a non-obvious iteration schema. :)
- tzs 5y agoI took that into account, although it may not have been clear because I tried to describe it in words rather than code. What I was suggesting was something like this (in pseudocode): int previous_leftmost = 64; while (mask != 0) { leftmost = find_leftmost(mask); mask ^= 1u << leftmost; while (--previous_leftmost > leftmost) func_false(previous_leftmost); func_true(leftmost); }
- wmu 5y agoThanks, that's a really elegant approach.