当前位置：文江博客话题详情

显然无需循环即可找到 32 位数字的最高位组索引

发布于 2024-12-29 13:46:45 字数 66 浏览 2 评论 0原文

这是一个困难的问题（至少我很难过：P）：

在不使用任何循环的情况下找到 32 位数字的最高位集的索引。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

浅唱々樱花落 2025-01-05 13:46:45

基准解决方案的答案，

非常有趣的问题，我将为您提供使用循环的

uint8_t highestBitIndex( uint32_t n )
{
    uint8_t r = 0;
    while ( n >>= 1 )
        r++;
    return r;
}

这有助于更好地理解问题，但效率非常低。

使用日志的解决方案

这种方法也可以通过日志方法进行总结

uint8_t highestSetBitIndex2(uint32_t n) {
    return (uint8_t)(log(n) / log(2));
}

，但是它的效率也很低（甚至比上面的方法还要低，请参阅基准测试）

使用内置指令的解决方案

uint8_t highestBitIndex3( uint32_t n )
{
    return 31 - __builtin_clz(n);
}

这种解决方案虽然非常高效，但其缺点是它只适用于特定的编译器（gcc 和 clang 都可以）和特定的平台上。

注意：如果我们想要索引，则为 31 而不是 32

具有内在的解决方案

#include <x86intrin.h> 

uint8_t highestSetBitIndex5(uint32_t n)
{
    return _bit_scan_reverse(n); // undefined behavior if n == 0
}

这将在汇编级别调用 bsr 指令

使用内联汇编的解决方案

LZCNT 和 BSR 可以用以下函数在汇编中进行总结：

uint8_t highestSetBitIndex4(uint32_t n) // undefined behavior if n == 0
{
    __asm__ __volatile__ (R"(
        .intel_syntax noprefix
            bsr eax, edi
        .att_syntax noprefix
        )"
            );
}

uint8_t highestSetBitIndex7(uint32_t n) // undefined behavior if n == 0
{
    __asm__ __volatile__ (R"(.intel_syntax noprefix
        lzcnt ecx, edi
        mov eax, 31
        sub eax, ecx
        .att_syntax noprefix
    )");
}

NB ：除非您知道自己在做什么，否则不要使用

使用查找表和幻数乘法的解决方案（可能是最好的据我所知）

首先，您使用以下函数来清除除最高位之外的所有位：

uint32_t keepHighestBit( uint32_t n )
{
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

信用：这个想法来自Henry S. Warren, Jr. 在他的书 Hacker's Delight

然后我们使用基于 DeBruijn 序列的算法执行一种二分搜索：

uint8_t highestBitIndex8( uint32_t b )
{
    static const uint32_t deBruijnMagic = 0x06EB14F9; // equivalent to 0b111(0xff ^ 3)
    static const uint8_t deBruijnTable[64] = {
         0,  0,  0,  1,  0, 16,  2,  0, 29,  0, 17,  0,  0,  3,  0, 22,
        30,  0,  0, 20, 18,  0, 11,  0, 13,  0,  0,  4,  0,  7,  0, 23,
        31,  0, 15,  0, 28,  0,  0, 21,  0, 19,  0, 10, 12,  0,  6,  0,
         0, 14, 27,  0,  0,  9,  0,  5,  0, 26,  8,  0, 25,  0, 24,  0,
     };
    return deBruijnTable[(keepHighestBit(b) * deBruijnMagic) >> 26];
}

另一个版本：

void propagateBits(uint32_t *n) {
    *n |= *n >> 1;
    *n |= *n >> 2;
    *n |= *n >> 4;
    *n |= *n >> 8;
    *n |= *n >> 16;
}

uint8_t highestSetBitIndex8(uint32_t b)
{
  static const uint32_t Magic = (uint32_t) 0x07C4ACDD;

  static const int BitTable[32] = {
     0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7,
    19, 27, 23,  6, 26,  5,  4, 31,
  };
  propagateBits(&b);

  return BitTable[(b * Magic) >> 27];
}

基准测试，调用次数为 1 亿次

使用 g++ -std=c++17 HighestSetBit.cpp 进行编译的 -O3 && ./a.out

highestBitIndex1  136.8 ms (loop)  
highestBitIndex2  183.8 ms (log(n) / log(2)) 
highestBitIndex3   10.6 ms (de Bruijn lookup Table with power of two, 64 entries)
highestBitIndex4   4.5 ms (inline assembly bsr)
highestBitIndex5   6.7 ms (intrinsic bsr)
highestBitIndex6   4.7 ms (gcc lzcnt)
highestBitIndex7   7.1 ms (inline assembly lzcnt)
highestBitIndex8  10.2 ms (de Bruijn lookup Table, 32 entries)

如果您关注的是可移植性，我个人会选择 HighBitIndex8，否则内置的 gcc 就很好了。

Very interesting question, I will provide you an answer with benchmark

Solution using a loop

uint8_t highestBitIndex( uint32_t n )
{
    uint8_t r = 0;
    while ( n >>= 1 )
        r++;
    return r;
}

This help to better understand the question but is highly inefficient.

Solution using log

This approach can also be summarize by the log method

uint8_t highestSetBitIndex2(uint32_t n) {
    return (uint8_t)(log(n) / log(2));
}

However it is also inefficient (even more than above one, see benchmark)

Solution using built-in instruction

uint8_t highestBitIndex3( uint32_t n )
{
    return 31 - __builtin_clz(n);
}

This solution, while very efficient, suffer from the fact that it only work with specific compilers (gcc and clang will do) and on specific platforms.

NB: It is 31 and not 32 if we want the index

Solution with intrinsic

#include <x86intrin.h> 

uint8_t highestSetBitIndex5(uint32_t n)
{
    return _bit_scan_reverse(n); // undefined behavior if n == 0
}

This will call the bsr instruction at assembly level

Solution using inline assembly

LZCNT and BSR can be summarize in assembly with the below functions:

uint8_t highestSetBitIndex4(uint32_t n) // undefined behavior if n == 0
{
    __asm__ __volatile__ (R"(
        .intel_syntax noprefix
            bsr eax, edi
        .att_syntax noprefix
        )"
            );
}

uint8_t highestSetBitIndex7(uint32_t n) // undefined behavior if n == 0
{
    __asm__ __volatile__ (R"(.intel_syntax noprefix
        lzcnt ecx, edi
        mov eax, 31
        sub eax, ecx
        .att_syntax noprefix
    )");
}

NB: Do Not Use unless you know what you are doing

Solution using lookup table and magic number multiplication (probably the best AFAIK)

First you use the following function to clear all the bits except the highest one:

uint32_t keepHighestBit( uint32_t n )
{
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

Credit: The idea come from Henry S. Warren, Jr. in his book Hacker's Delight

Then we use an algorithm based on DeBruijn's Sequence to perform a kind of binary search:

uint8_t highestBitIndex8( uint32_t b )
{
    static const uint32_t deBruijnMagic = 0x06EB14F9; // equivalent to 0b111(0xff ^ 3)
    static const uint8_t deBruijnTable[64] = {
         0,  0,  0,  1,  0, 16,  2,  0, 29,  0, 17,  0,  0,  3,  0, 22,
        30,  0,  0, 20, 18,  0, 11,  0, 13,  0,  0,  4,  0,  7,  0, 23,
        31,  0, 15,  0, 28,  0,  0, 21,  0, 19,  0, 10, 12,  0,  6,  0,
         0, 14, 27,  0,  0,  9,  0,  5,  0, 26,  8,  0, 25,  0, 24,  0,
     };
    return deBruijnTable[(keepHighestBit(b) * deBruijnMagic) >> 26];
}

Another version:

void propagateBits(uint32_t *n) {
    *n |= *n >> 1;
    *n |= *n >> 2;
    *n |= *n >> 4;
    *n |= *n >> 8;
    *n |= *n >> 16;
}

uint8_t highestSetBitIndex8(uint32_t b)
{
  static const uint32_t Magic = (uint32_t) 0x07C4ACDD;

  static const int BitTable[32] = {
     0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7,
    19, 27, 23,  6, 26,  5,  4, 31,
  };
  propagateBits(&b);

  return BitTable[(b * Magic) >> 27];
}

Benchmark with 100 million calls

compiling with g++ -std=c++17 highestSetBit.cpp -O3 && ./a.out

highestBitIndex1  136.8 ms (loop)  
highestBitIndex2  183.8 ms (log(n) / log(2)) 
highestBitIndex3   10.6 ms (de Bruijn lookup Table with power of two, 64 entries)
highestBitIndex4   4.5 ms (inline assembly bsr)
highestBitIndex5   6.7 ms (intrinsic bsr)
highestBitIndex6   4.7 ms (gcc lzcnt)
highestBitIndex7   7.1 ms (inline assembly lzcnt)
highestBitIndex8  10.2 ms (de Bruijn lookup Table, 32 entries)

I would personally go for highestBitIndex8 if portability is your focus, else gcc built-in is nice.

回复收藏 0 原文

眼藏柔 2025-01-05 13:46:45

使用递归：

int firstset(int bits) {        
     return (bits & 0x80000000) ? 31 : firstset((bits << 1) | 1) - 1;
}

假设[31,..,0]索引
如果没有设置位则返回-1
| 1 通过限制移位次数直到达到 1 来防止堆栈溢出 (32)
非尾递归:)

With recursion:

int firstset(int bits) {        
     return (bits & 0x80000000) ? 31 : firstset((bits << 1) | 1) - 1;
}

Assumes [31,..,0] indexing
Returns -1 if no bits set
| 1 prevents stack overflow by capping the number of shifts until a 1 is reached (32)
Not tail recursive :)

回复收藏 0 原文

眼泪淡了忧伤 2025-01-05 13:46:45

以二为底的对数下限应该可以解决问题（尽管你必须特殊情况 0）。

Floor of log base 2 of 0001 is 0 (bit with index 0 is set).
 "           "      of 0010 is 1 (bit with index 1 is set).
 "           "      of 0011 is 1 (bit with index 1 is set).
 "           "      of 0100 is 2 (bit with index 2 is set).
and so on.

顺便说一句，这实际上是一个非常糟糕的面试问题（我是作为一个为潜在候选人进行技术面试的人说的），因为它确实与您在实际编程中所做的任何事情都不相符。

您的老板不会有一天对您说：“嘿，所以我们对这项最新功能有一项紧急工作，并且需要在没有循环的情况下实现！”

Floor of logarithm-base-two should do the trick (though you have to special-case 0).

Floor of log base 2 of 0001 is 0 (bit with index 0 is set).
 "           "      of 0010 is 1 (bit with index 1 is set).
 "           "      of 0011 is 1 (bit with index 1 is set).
 "           "      of 0100 is 2 (bit with index 2 is set).
and so on.

On an unrelated note, this is actually a pretty terrible interview question (I say this as someone who does technical interviews for potential candidates), because it really doesn't correspond to anything you do in practical programming.

Your boss isn't going to come up to you one day and say "hey, so we have a rush job for this latest feature, and it needs to be implemented without loops!"

回复收藏 0 原文

╰ゝ天使的微笑 2025-01-05 13:46:45

你可以这样做（未优化）：

int index = 0;
uint32_t temp = number;

if ((temp >> 16) != 0) {
    temp >>= 16;
    index += 16;
}

if ((temp >> 8) != 0) {
    temp >>= 8
    index += 8;
}

...

You could do it like this (not optimised):

int index = 0;
uint32_t temp = number;

if ((temp >> 16) != 0) {
    temp >>= 16;
    index += 16;
}

if ((temp >> 8) != 0) {
    temp >>= 8
    index += 8;
}

...

回复收藏 0 原文

鲜肉鲜肉永远不皱 2025-01-05 13:46:45

抱歉打扰了旧线程，但是这个怎么样

inline int ilog2(unsigned long long i) {
  union { float f; int i; } = { i }; 
  return (u.i>>23)-27;
}
...
int highest=ilog2(x); highest+=(x>>highest)-1;
// and in case you need it
int lowest = ilog2((x^x-1)+1)-1;

sorry for bumping an old thread, but how about this

inline int ilog2(unsigned long long i) {
  union { float f; int i; } = { i }; 
  return (u.i>>23)-27;
}
...
int highest=ilog2(x); highest+=(x>>highest)-1;
// and in case you need it
int lowest = ilog2((x^x-1)+1)-1;

回复收藏 0 原文

℉絮湮 2025-01-05 13:46:45

这可以通过二分搜索来完成，将 O(N)（对于 N 位字）的复杂度降低到 O(log(N))。一种可能的实现是：

int highest_bit_index(uint32_t value)
{ 
  if(value == 0) return 0;
  int depth = 0;
  int exponent = 16;

  while(exponent > 0)
  {
    int shifted = value >> (exponent);
    if(shifted > 0)
    {
      depth += exponent;
      if(shifted == 1) return depth + 1;
      value >>= exponent;
    }
    exponent /= 2;
  }

  return depth + 1;
}

输入是32位无符号整数。
它有一个循环，可以转换为 5 级 if 语句，因此会产生 32 个左右的 if 语句。你也可以使用递归来摆脱循环，或者绝对邪恶的“goto”；）

this can be done as a binary search, reducing complexity of O(N) (for an N-bit word) to O(log(N)). A possible implementation is:

int highest_bit_index(uint32_t value)
{ 
  if(value == 0) return 0;
  int depth = 0;
  int exponent = 16;

  while(exponent > 0)
  {
    int shifted = value >> (exponent);
    if(shifted > 0)
    {
      depth += exponent;
      if(shifted == 1) return depth + 1;
      value >>= exponent;
    }
    exponent /= 2;
  }

  return depth + 1;
}

the input is a 32 bit unsigned integer.
it has a loop that can be converted into 5 levels of if-statements , therefore resulting in 32 or so if-statements. you could also use recursion to get rid of the loop, or the absolutely evil "goto" ;)

回复收藏 0 原文

演多会厌 2025-01-05 13:46:45

让
n - 要识别位位置的十进制数
start - 表示十进制值 ( 1 << 32 ) - 2147483648
bitLocation - 指示设置为 1 的位位置

public int highestBitSet(int n, long start, int bitLocation)
{
    if (start == 0)
    {
        return 0;
    }
    if ((start & n) > 0)
    {
        return bitLocation;
    }
    else
    {
        return highestBitSet(n, (start >> 1), --bitLocation);
    }
}

    long i = 1;
    long startIndex = (i << 31);
    int bitLocation = 32;
    int value = highestBitSet(64, startIndex, bitLocation);
    System.out.println(value);

Let
n - Decimal number for which bit location to be identified
start - Indicates decimal value of ( 1 << 32 ) - 2147483648
bitLocation - Indicates bit location which is set to 1

public int highestBitSet(int n, long start, int bitLocation)
{
    if (start == 0)
    {
        return 0;
    }
    if ((start & n) > 0)
    {
        return bitLocation;
    }
    else
    {
        return highestBitSet(n, (start >> 1), --bitLocation);
    }
}

    long i = 1;
    long startIndex = (i << 31);
    int bitLocation = 32;
    int value = highestBitSet(64, startIndex, bitLocation);
    System.out.println(value);

回复收藏 0 原文

我要还你自由 2025-01-05 13:46:45

int high_bit_set(int n, int pos)
{
if(pos<0) 
return -1;
else
return (0x80000000 & n)?pos:high_bit_set((n<<1),--pos);
}

main()
{
int n=0x23;
int high_pos = high_bit_set(n,31);
printf("highest index = %d",high_pos);
}

从主调用函数 high_bit_set(int n , int pos) 中输入值 n，默认 31 作为最高位置。功能就像上面一样。

int high_bit_set(int n, int pos)
{
if(pos<0) 
return -1;
else
return (0x80000000 & n)?pos:high_bit_set((n<<1),--pos);
}

main()
{
int n=0x23;
int high_pos = high_bit_set(n,31);
printf("highest index = %d",high_pos);
}

From your main call function high_bit_set(int n , int pos) with the input value n, and default 31 as the highest position. And the function is like above.

回复收藏 0 原文

喜你已久 2025-01-05 13:46:45

Paislee 的解决方案实际上很容易进行尾递归，不过，它比建议的 Floor(log2(n)); 慢得多。

int firstset_tr(int bits, int final_dec) {

     // pass in 0 for final_dec on first call, or use a helper function

     if (bits & 0x80000000) {
      return 31-final_dec;
     } else {
      return firstset_tr( ((bits << 1) | 1), final_dec+1 );
     }
}

此功能也适用于其他位大小，只需更改检查即可，
例如

if (bits & 0x80) {   // for 8-bit
  return 7-final_dec;
}

Paislee's solution is actually pretty easy to make tail-recursive, though, it's a much slower solution than the suggested floor(log2(n));

int firstset_tr(int bits, int final_dec) {

     // pass in 0 for final_dec on first call, or use a helper function

     if (bits & 0x80000000) {
      return 31-final_dec;
     } else {
      return firstset_tr( ((bits << 1) | 1), final_dec+1 );
     }
}

This function also works for other bit sizes, just change the check,
e.g.

if (bits & 0x80) {   // for 8-bit
  return 7-final_dec;
}

回复收藏 0 原文

傾旎 2025-01-05 13:46:45

请注意，您想要做的是计算整数的整数 log2，

#include <stdio.h>
#include <stdlib.h>

unsigned int
Log2(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1; int k=0;
    for( step = 1; step < bits; ) {
        n |= (n >> step);
        step *= 2; ++k;
    }
    //printf("%ld %ld\n",x, (x - (n >> 1)) );
    return(x - (n >> 1));
}

请注意，您可以尝试一次搜索超过 1 位。

unsigned int
Log2_a(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1;
    int step2 = 0;
    //observe that you can move 8 bits at a time, and there is a pattern...
    //if( x>1<<step2+8 ) { step2+=8;
        //if( x>1<<step2+8 ) { step2+=8;
            //if( x>1<<step2+8 ) { step2+=8;
            //}
        //}
    //}
    for( step2=0; x>1L<<step2+8; ) {
        step2+=8;
    }
    //printf("step2 %d\n",step2);
    for( step = 0; x>1L<<(step+step2); ) {
        step+=1;
        //printf("step %d\n",step+step2);
    }
    printf("log2(%ld) %d\n",x,step+step2);
    return(step+step2);
}

这种方法使用了二分搜索

unsigned int
Log2_b(unsigned long x)
{
    unsigned long n = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int hbit = bits-1;
    unsigned int lbit = 0;
    unsigned long guess = bits/2;
    int found = 0;

    while ( hbit-lbit>1 ) {
        //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        //when value between guess..lbit
        if( (x<=(1L<<guess)) ) {
           //printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
            hbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
        //when value between hbit..guess
        //else
        if( (x>(1L<<guess)) ) {
            //printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
            lbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
    }
    if( (x>(1L<<guess)) ) ++guess;
    printf("log2(x%ld)=r%d\n",x,guess);
    return(guess);
}

另一种二分搜索方法，也许更具可读性，

unsigned int
Log2_c(unsigned long x)
{
    unsigned long v = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int step = bits;
    unsigned int res = 0;
    for( step = bits/2; step>0; )
    {
        //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
        while ( v>>step ) {
            v>>=step;
            res+=step;
            //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
        }
        step /= 2;
    }
    if( (x>(1L<<res)) ) ++res;
    printf("log2(x%ld)=r%ld\n",x,res);
    return(res);
}

并且因为您将想要测试这些，

int main()
{
    unsigned long int x = 3;
    for( x=2; x<1000000000; x*=2 ) {
        //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
        printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
        printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
        printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
    }
    return(0);
}

Note that what you are trying to do is calculate the integer log2 of an integer,

#include <stdio.h>
#include <stdlib.h>

unsigned int
Log2(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1; int k=0;
    for( step = 1; step < bits; ) {
        n |= (n >> step);
        step *= 2; ++k;
    }
    //printf("%ld %ld\n",x, (x - (n >> 1)) );
    return(x - (n >> 1));
}

Observe that you can attempt to search more than 1 bit at a time.

unsigned int
Log2_a(unsigned long x)
{
    unsigned long n = x;
    int bits = sizeof(x)*8;
    int step = 1;
    int step2 = 0;
    //observe that you can move 8 bits at a time, and there is a pattern...
    //if( x>1<<step2+8 ) { step2+=8;
        //if( x>1<<step2+8 ) { step2+=8;
            //if( x>1<<step2+8 ) { step2+=8;
            //}
        //}
    //}
    for( step2=0; x>1L<<step2+8; ) {
        step2+=8;
    }
    //printf("step2 %d\n",step2);
    for( step = 0; x>1L<<(step+step2); ) {
        step+=1;
        //printf("step %d\n",step+step2);
    }
    printf("log2(%ld) %d\n",x,step+step2);
    return(step+step2);
}

This approach uses a binary search

unsigned int
Log2_b(unsigned long x)
{
    unsigned long n = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int hbit = bits-1;
    unsigned int lbit = 0;
    unsigned long guess = bits/2;
    int found = 0;

    while ( hbit-lbit>1 ) {
        //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        //when value between guess..lbit
        if( (x<=(1L<<guess)) ) {
           //printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
            hbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
        //when value between hbit..guess
        //else
        if( (x>(1L<<guess)) ) {
            //printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
            lbit=guess;
            guess=(hbit+lbit)/2;
            //printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
        }
    }
    if( (x>(1L<<guess)) ) ++guess;
    printf("log2(x%ld)=r%d\n",x,guess);
    return(guess);
}

Another binary search method, perhaps more readable,

unsigned int
Log2_c(unsigned long x)
{
    unsigned long v = x;
    unsigned int bits = sizeof(x)*8;
    unsigned int step = bits;
    unsigned int res = 0;
    for( step = bits/2; step>0; )
    {
        //printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
        while ( v>>step ) {
            v>>=step;
            res+=step;
            //printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
        }
        step /= 2;
    }
    if( (x>(1L<<res)) ) ++res;
    printf("log2(x%ld)=r%ld\n",x,res);
    return(res);
}

And because you will want to test these,

int main()
{
    unsigned long int x = 3;
    for( x=2; x<1000000000; x*=2 ) {
        //printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
        printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
        printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
        printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
    }
    return(0);
}

回复收藏 0 原文