仅使用C中的按位运算符来计算log²(x)的底数 [英] Computing the floor of log₂(x) using only bitwise operators in C

问题描述

对于作业，使用C，我应该编写一个仅使用运算符! ~ & ^ | + << >>来找到大于0的对数为2的对数的程序.我知道我应该右移几次，但是我不知道如何在没有任何循环或if的情况下跟踪次数.我已经在这个问题上待了好几天了，所以能提供任何帮助.

For homework, using C, I'm supposed to make a program that finds the log base 2 of a number greater than 0 using only the operators ! ~ & ^ | + << >>. I know that I'm supposed to shift right a number of times, but I don't know how to keep track of the number of times without having any loops or ifs. I've been stuck on this question for days, so any help is appreciated.

int ilog2(int x) {
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
}

这是我到目前为止所拥有的.我将最重要的部分传递到了最后.

This is what I have so far. I pass the most significant bit to the end.

推荐答案

这将获取数字的logbase2的下限.

This gets the floor of logbase2 of a number.

int ilog2(int x) {

    int i, j, k, l, m;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);

    // i = 0x55555555 
    i = 0x55 | (0x55 << 8); 
    i = i | (i << 16);

    // j = 0x33333333 
    j = 0x33 | (0x33 << 8);
    j = j | (j << 16);

    // k = 0x0f0f0f0f 
    k = 0x0f | (0x0f << 8);
    k = k | (k << 16);

    // l = 0x00ff00ff 
    l = 0xff | (0xff << 16);

    // m = 0x0000ffff 
    m = 0xff | (0xff << 8);

    x = (x & i) + ((x >> 1) & i);
    x = (x & j) + ((x >> 2) & j);
    x = (x & k) + ((x >> 4) & k);
    x = (x & l) + ((x >> 8) & l);
    x = (x & m) + ((x >> 16) & m);
    x = x + ~0;
    return x; 
}

这篇关于仅使用C中的按位运算符来计算log²(x)的底数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！