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); }

Auto comment: topic has been updated by bajuddin15 (previous revision, new revision, compare).__lg(n) will do your work.

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

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

this blog is copy pasted from here

really

idk why he didn't even bother using google

__builtin_clz or __builtin_clzll

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

__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.

Ah that's what you meant, ok thanks. 👍

In C++20 you can use

`std::bit_width(x) - 1`

.