4

For an unsigned integer j, the operation j&(-j) clears all but the least significant 1 bit, where -j is the negative of j treating j as a signed integer. https://en.wikipedia.org/wiki/Find_first_set

Is there a similar simple operation that clears all but the most significant 1 bit?

An obvious solution is using clz (count leading zeros) operation which is present in nearly all contemporary processors. There is also a question Previous power of 2 with an answer that is said to work even faster than clz on old AMD processors. See also What is fastest method to calculate a number having only bit set which is the most significant digit set in another number?

My question is whether there is something simpler than using clz which may not be easily accessible in certain languages. Note that I need the most significant 1 bit itself, not its position (logarithm).

Viktor
  • 472
  • 5
  • 14
  • 1
    Possible duplicate of [Previous power of 2](https://stackoverflow.com/questions/2679815/previous-power-of-2) – Nate Eldredge Mar 01 '19 at 04:57
  • @NateEldredge I cannot see how my question may duplicate the question on the "Previous power of two". And there is clearly no answer to my question. – Viktor Mar 01 '19 at 05:57
  • 2
    "Clear all but most significant 1 bit" is equivalent to "round down to a power of two", which is what the answers to that question do. Try them out and see. The fact that none of them is "similarly simple" to `j&(-j)` suggests that nobody knows of such a simple algorithm for this. – Nate Eldredge Mar 01 '19 at 06:12
  • @NateEldredge I have edited my question according to your remark. – Viktor Mar 01 '19 at 06:39
  • 1
    Possible duplicate of [What is fastest method to calculate a number having only bit set which is the most significant digit set in another number?](https://stackoverflow.com/questions/3407070/what-is-fastest-method-to-calculate-a-number-having-only-bit-set-which-is-the-mo) – phuclv Mar 01 '19 at 10:31
  • 1
    [What is the fastest way to get the power of 2 less than a certain number?](https://stackoverflow.com/q/25220184/995714), [What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?](https://stackoverflow.com/q/671815/995714) – phuclv Mar 01 '19 at 10:35
  • @phuclv I need the most significant 1 bit itself, not its position (logarithm). Of course, if one has the position then that bit is obtained by bit shift. But nonexistence of a "simple" formula for the position does not imply the nonexistence for the bit itself, as it is the case for the least significant set bit. – Viktor Mar 01 '19 at 11:32
  • @phuclv I have added the link to https://stackoverflow.com/questions/3407070/what-is-fastest-method-to-calculate-a-number-having-only-bit-set-which-is-the-mo – Viktor Mar 01 '19 at 11:37
  • 1
    in any case there were already tons of duplicate questions of yours. And *simpler* is too broad, just like "fastest". Speed depends on the compiler and the platform, and simplicity depends on the view of the reader – phuclv Mar 01 '19 at 12:21

1 Answers1

1

For locate position of highest "1" in the word, I am using BSR assembly operation:

static inline uint32_t bsr(uint32_t x) {
  uint32_t rc = 0;
  __asm__("bsr %1,%0":"=r" (rc):"rm" (x));
  return rc;
}

It returns position of highest "1". For example, bsr(5) == 2. if needed this code for 64-bit "x", use bsrq instruction.

olegarch
  • 3,670
  • 1
  • 20
  • 19