Блог пользователя kingofnumbers

Автор kingofnumbers, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Try to get the logarithm of 2 :-)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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.

»
11 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    From Intel 80386, bsr instruction do it.

»
11 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится -66 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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!

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

    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.

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -13 Проголосовать: не нравится

        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.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
11 лет назад, # |
  Проголосовать: нравится +142 Проголосовать: не нравится
int msb(unsigned x) {
	union { double a; int b[2]; };
	a = x;
	return (b[1] >> 20) - 1023;
}
  • »
    »
    11 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    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!

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится

          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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
»
11 лет назад, # |
  Проголосовать: нравится -73 Проголосовать: не нравится

NOBODY CARES

»
8 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      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

»
5 лет назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -34 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится -45 Проголосовать: не нравится

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