Try to get the logarithm of 2 :-)

There is Integer.highestOneBit(int i) method in Java that returns int with leftmost bit set in x. It is implemented as follows:

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

As you can see, its running time actually depends on size of int as . Same way you can implement functions like numberOfLeadingZeros or bitCount. Look for source of java.lang.Integer for more details.

I had been where you are once! And the best I could think of is O(Log number of bits), for int its O(log 32), simply binary search that bit.

But in practice this tends to be slower than the linear search as the constant factor is quite big! Otherwise if you are interested in low level solutions, there are some special instructions that can get you what you want

See here

I don't think you can do it in O(1) — the computer does not recognize the "numbering" of bits, that's just the way we imagine it.

Why do you need it? Or better: do you really need this, wouldn't it be better to have an way with a small constant?

If N = 0 then .

int clz(int N) {
    return N ? 32 - __builtin_clz(N) : -inf;
}
int clz(unsigned long long N) {
    return N ? 64 - __builtin_clzll(N) : -inf;
}

You can read more about gcc builtins here.

To all commenters:

No offence, but wasn't I clear when I said that I want it:

1- O(1) time and memory

2- without using built-in functions that may not compile on all C++ compilers

and for log function it's too slow

Anyway, thank you all for your try.

You can calculate in advance this function for all integers from 0 to 2¹⁶ and save the values to the array. Then you for any integer x,

if ((x & ((1 << 16) - 1)) != 0) {
    return precalc[x & ((1 << 16) - 1)];
} else {
    return precalc[(x >> 16) & ((1 << 16) - 1)] + 16;
}

It is not O(1) memory, but in most cases you can afford to use additional 64 kilobytes.

int msb(unsigned x) {
	union { double a; int b[2]; };
	a = x;
	return (b[1] >> 20) - 1023;
}

NOBODY CARES

As mentioned already, for word size w, the naive approach takes w time. Binary search combined with bitshifting and masking takes O(lg w). It was shown in the "fusion tree" paper by Fredman and Willard that you can in fact do it in O(1) time, if you allow yourself to use multiplication. This is described in my lecture here: https://www.youtube.com/watch?v=3_o0-zPRQqw&list=PL2SOU6wwxB0uP4rJgf5ayhHWgw7akUWSf&index=2

__lg( a ^ (a & (a — 1)) )

hey the maximum possible number can be 63 if we assume N~10^18 so you need to compare the N with (1<<i) where i is from 0 to 63 and find the suitable value of i

for ints k = 32 - __builtin_clz(n) - 1 for long longs k = 64 - __builtin_clzll(n) - 1

Edit: Just realized you don't want builtin functions

just take the logarithm(base 2) of the number and store it in any integer variable and you will get the index of left most set bit. code:

int n; cin>>n; int x = log2(n); // use cmath library of c++ to use log2 function in you program. cout<<x; // here x will be the required index.

hope it helps.

Right most set bit = (n&~(n-1))