kingofnumbers's blog

how to find leftmost 1-bit in C++ in O(1)?
By kingofnumbers, 11 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.

  • Vote: I like it
  • +21
  • Vote: I do not like it

Comments Comments (46)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try to get the logarithm of 2 :-)

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

    You are wrong. Log(2,n) is the minimal x, such that 2^x>=n. We can easily see, that the maximal x, such that 2^x<=n is Log(2,n)-1 if n is not power of two and Log(2,n) otherwise. You can see the code to understand better : http://pastie.org/8617128

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

    Since log() takes just doubles, its range+precision is heavily limited.

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

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.

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

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

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

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?

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

    But if we find a way to mask out all bits except the leftmost? Then we can use lookup array of 32 elements to return the number of this bit. And it would be O(1)

    Though I'm not sure I know how to perform such masking.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Dependent on 32, the integer size. Once again, dependent on size. That's what the thread author wants, and that's what I'm claiming impossible.

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

    From Intel 80386, bsr instruction do it.

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

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.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it -66 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    To be absolutely clear: if you'll use an ordinary binary search, it'll work in O(1), since our integer size is constant. Just use it!

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +25 Vote: I do not like it

    It is however still unclear whether you want a practical or theoretical solution.

    If you need this in practice, perhaps the stackoverflow answer above covers it entirely with its multiple links. One can say the currently popular word sizes are constants, so many of the presented solutions can be considered as taking O(1) time and memory. If you insist on not using the processor instruction, something along the lines of these two answers will perhaps be the fastest. Also note that if your number is guaranteed to be a power of two, you can find the logarithm in O(1) time and O(bits) memory in the precalculated array.

    If you are interested in the theoretical question (that is, find the most significant bit in O(1) when the size of the word tends to infinity, but word operations still take O(1)), then the requirement to use C++ looks strange. Perhaps it is then better to explicitly state which operations are available (for example, only arithmetic operations, bitwise logical operations and bitwise shifts, but not bit-scan-reverse nor any other modern processor instructions). At a glance, it looks to me like there is no O(1) solution, but I have no proof of that so far. And anyway, an existence of such a solution will not guarantee it to be feasible on modern hardware.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +20 Vote: I do not like it

      that's good question indeed, actually I want both (practical or theoretical) =D.

      after reading all comments and googling a lot I agree with you that there's no theoretical O(1) time and memory solution (or at least it's unknown yet)

      but there's still two good choices practically, the first is using built-in functions , actually I didn't want to use them because I'm not familiar with all C++ compilers so I wanted to use standard methods that successfully compile on all C++ compilers, and the second choice is using the idea in link you gave me.

      there's two good choices, so I wrote simple C++ code to test whether built-in functions are faster or the idea in previous link is faster, and it turned out that built-in function are faster.

      so I decided to do this during the contests:

      1- I will try to use built-in functions.

      2- if I wasn't familiar with the C++ compiler used in this contest and I faced compile error when using the built-in functions then I will use the second choice.

      thank you all very much for helping me and sorry if I was so offensive.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -13 Vote: I do not like it

        If you want a theoretical answer. Everything that uses that int has 32 bits, is O(1), because 32 is O(1), if the range of integers that you can represent with your type is unbounded, it cannot be O(1), so it's easy to determine if you have an O(1) algorithm or not.

        → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

You can calculate in advance this function for all integers from 0 to 216 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.

→ Reply
»
11 years ago, # |
  Vote: I like it +142 Vote: I do not like it 
int msb(unsigned x) {
	union { double a; int b[2]; };
	a = x;
	return (b[1] >> 20) - 1023;
}
→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    awesome!

    it's even a little bit faster than built-in functions , but I can't understand how it's work. since it's first time I see "union" operation , I tried to read tutorials about "union" but still don't understand how your code works!

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

      I converts number to double and then read bits of number's representation in IEEE 754. In fact, exponent is read.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        I just want to clarify one point: Is it always the case that b[1] represents 32 bits containing the sign bit and 11-bit exponent?

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

          The C++ standard doesn't specify the binary representation of integral or floating-point types as well as type sizes. Means that b[1] is not necessary 32 bits and it's not necessary it shares any bits with a. Also, according to C++ standard writing to one member of union and reading from another results in an unspecified value. However, on practice all compilers allow type punning through unions and this code will work on most platforms that use little endian format and support IEEE 754. One can cover wider range of platforms by using constants from std::numeric_limits and by replacing int b[2] with int64_t b to fix endianness and int's size issues.

          → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Speed test: http://ideone.com/KdjzTB

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

NOBODY CARES

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

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

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

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

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

    (a & (a — 1)) ) part will remove leftmost set bit, how does it help with this after exor

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

      If we make XOR between a and a without the leftmost bit we will obtain a number that only the leftmost bit of a will be active because the rest of the bits will be equal. the log_2 of this number is the position of this bit

      → Reply
»
5 years ago, # |
  Vote: I like it -56 Vote: I do not like it

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

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

    I bet he was looking forward to this reply.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    There are two reasons for downvotes (not me)
    1] whenever you are commenting you should actually see the date of blog posted and comment accordingly.
    2] see if your are spamming,by commenting same answer.
    P.S.- There is no rule book to understand all this, but many new coders don't know this generalised stuff, hence commenting.

    → Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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.

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

    thanks for replying with a wrong answer after 7 years

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

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

→ Reply