bajuddin15's blog

how to find leftmost 1-bit in C++ ?
By bajuddin15, history, 3 years ago, In English

how to find leftmost 1-bit in C++ ?

in other word I want to find biggest k so that 2^k <= N for some given number N

for example if N=10 then k=3

I want an O(1) time and memory solution and also without using built-in functions that may not compile in ALL C++ compilers.

thank you in advance.

plz tell me this is correct or not ?

------------------------------------------- int highestOneBit(int i) { i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i — (i >> 1); }

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

__lg(n) will do your work.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    without using built-in functions that may not compile in ALL C++ compilers?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I think this works for $$$O(log(log(n)))$$$. In order for it to work for $$$O(1)$$$, you need to add: 

    #pragma GCC target ("popcnt")
    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

this blog is copy pasted from here

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

__builtin_clz or __builtin_clzll

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in other word I want to find biggest k so that 2^k <= N for some given number N

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      __builtin_clz does almost this. It counts number of leading zeros in binary, so 32 — return value is number of digits in binary representation of a number which is almost what you want to find. Now you need to just correct some off-by-one errors in what I said here.

      → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

In C++20 you can use std::bit_width(x) - 1.

→ Reply