僅使用C中的按位運算符來計算log_2（x）的底面

對於使用C的作業，我應該創建一個程序，僅使用操作符來查找大於0的數字的日誌基2！〜&^| + < < >>。我知道我應該多次輪換，但我不知道如何跟蹤沒有任何循環或ifs的次數。我一直在這個問題上堅持了幾天，所以任何幫助表示讚賞。僅使用C中的按位運算符來計算log_2（x）的底面

int ilog2(int x) { 

    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >> 16); 

}

這是我到目前爲止。我把最重要的一點傳遞給了最後。

來源

2014-01-29 Brett Cox

顯示你做了什麼。 – chux

最簡單的解決方法是返回第一個非零位的位置。 –

這些「按位」問題還有另一個允許使用「+」...... –

這得到了一個數字的logbase2的地板。

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; 
}

來源

2014-01-29 21:07:19

這可能是log10（x）或ln（x），但肯定不是log2（x）。 –

@kuroineko：你爲什麼這麼說？ –

這個答案很聰明，我喜歡。我不明白'm = 0xff |的意思（0xff << 8）;'雖然......爲什麼不只是'm = 0xffff'？ –

您的結果只是最高非空位的排名。

int log2_floor (int x) 
{ 
    int res = -1; 
    while (x) { res++ ; x = x >> 1; } 
    return res; 
}

一種可能的解決方案就是採取這樣的方法：

它是基於對數的加和：
日誌（2 ^Ñ X）=登錄（X ）+ n

讓x是2n比特的數目（例如，對於32比特，n = 16）。

如果X > 2 ^Ñ，我們可以定義X使得 X = 2 ^Ñ X ，我們可以說， E（log （x ））= n + E（lo克（X ））
我們可以計算 X 用二進制移位： X = X >> N

否則我們可以簡單地設置X = X

我們現在每一步面臨的X

剩餘的上限或下限一半分裂X同樣的問題了一半，我們最終可以計算E（登錄（X））：

int log2_floor (unsigned x) 
{ 
    #define MSB_HIGHER_THAN(n) (x &(~((1<<n)-1))) 
    int res = 0; 
    if MSB_HIGHER_THAN(16) {res+= 16; $x >>= 16;} 
    if MSB_HIGHER_THAN(8) {res+= 8; $x >>= 8;} 
    if MSB_HIGHER_THAN(4) {res+= 4; $x >>= 4;} 
    if MSB_HIGHER_THAN(2) {res+= 2; $x >>= 2;} 
    if MSB_HIGHER_THAN(1) {res+= 1;} 
    return res; 
}

由於您的虐待狂老師說你不能使用循環，我們可以通過左右計算值破解我們的方式，將是n正工商業污水附加費的情況下，噸，否則爲0，從而對增加或換檔的效果：

#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0(n) (((-(x>>n))>>n)&n)

如果-運營商也由你psychopatic老師禁止（因爲處理器能夠處理2的補一樣好位運算這是愚蠢的），你可以在上面的公式

#define N_IF_MSB_HIGHER_THAN_N_OR_ELSE_0_WITH_NO_MINUS(n) (((~(x>>n)+1)>>n)&n)

，我們將縮短爲NIMHTNOE0WNM在可讀性使用-x = ~x+1。

此外，我們將使用|而不是+，因爲我們知道他們將不會攜帶。

這裏的例子是32位整數，但如果你設法找到支持這個大整數值的語言，你可以使它在64,128,256,512或1024位整數上工作。

int log2_floor (unsigned x) 
{ 
    #define NIMHTNOE0WNM(n) (((~(x>>n)+1)>>n)&n) 

    int res, n; 

    n = NIMHTNOE0WNM(16); res = n; x >>= n; 
    n = NIMHTNOE0WNM(8); res |= n; x >>= n; 
    n = NIMHTNOE0WNM(4); res |= n; x >>= n; 
    n = NIMHTNOE0WNM(2); res |= n; x >>= n; 
    n = NIMHTNOE0WNM(1); res |= n; 
    return res; 
}

啊，但也許你也禁止使用#define呢？在這種情況下，我不能爲你做更多的事情，除非建議你用老版本的K & R.

這會導致無用的混淆代碼，它會釋放出未清洗的70年代黑客的強烈氣味。

如果不是所有的處理器執行特定的「計數前導零」指令（例如，clz對ARM，bsr在x86或cntlz在PowerPC），可以做的伎倆沒有這些麻煩。

來源

2014-01-29 21:37:06

不允許循環。 – chepner

好的，對不起，我沒有仔細閱讀這個問題。感謝downvotes雨，順便說一句。看起來，黑客仍然非常活躍並且踢腿。 –

假設一個32位unsigned int：

unsigned int ulog2 (unsigned int u) 
{ 
    unsigned int s, t; 

    t = (u > 0xffff) << 4; u >>= t; 
    s = (u > 0xff ) << 3; u >>= s, t |= s; 
    s = (u > 0xf ) << 2; u >>= s, t |= s; 
    s = (u > 0x3 ) << 1; u >>= s, t |= s; 

    return (t | (u >> 1)); 
}

因爲我假定>，我想我會找到一個方法來擺脫它。

(u > 0xffff)相當於：((u >> 16) != 0)。如果減去借入：
((u >> 16) - 1)將設置msb，iff (u <= 0xffff)。將-1替換爲+(~0)（允許）。

所以條件：(u > 0xffff)被替換爲：(~((u >> 16) + ~0U)) >> 31

unsigned int ulog2 (unsigned int u) 
{ 
    unsigned int r = 0, t; 

    t = ((~((u >> 16) + ~0U)) >> 27) & 0x10; 
    r |= t, u >>= t; 
    t = ((~((u >> 8) + ~0U)) >> 28) & 0x8; 
    r |= t, u >>= t; 
    t = ((~((u >> 4) + ~0U)) >> 29) & 0x4; 
    r |= t, u >>= t; 
    t = ((~((u >> 2) + ~0U)) >> 30) & 0x2; 
    r |= t, u >>= t; 

    return (r | (u >> 1)); 
}

來源

2014-01-29 22:05:54

'>'運算符很像減法;似乎不被允許。 – Potatoswatter

你讓你可以使用&&使用&呢？有了，你可以做條件語句，而不需要if

if (cond) 
    doSomething();

可以

cond && doSomething();

否則可以做，如果你想分配值有條件像value = cond ? a : b;，那麼你可以用&

mask = -(cond != 0); // or mask = (cond != 0) << 31) >> 31; // assuming int is 32 bits and use 2's complement 
value = (mask & a) | (~mask & b);

做

部分其他方式：

int v; // 32-bit integer to find the log base 2 of 
int r; // result of log_2(v) goes here 
union { unsigned int u[2]; double d; } t; // temp 

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000; 
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v; 
t.d -= 4503599627370496.0; 
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

或

unsigned int v;   // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here 
register unsigned int shift; 

r =  (v > 0xFFFF) << 4; v >>= r; 
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift; 
shift = (v > 0xF ) << 2; v >>= shift; r |= shift; 
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift; 
             r |= (v >> 1);

另一種方式

uint32_t v; // find the log base 2 of 32-bit v 
int r;  // result goes here 

static const int MultiplyDeBruijnBitPosition[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 
}; 

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2; 
v |= v >> 4; 
v |= v >> 8; 
v |= v >> 16; 

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog

來源

2014-01-30 07:17:14

我也被分配了這個問題的功課，我花了很多時間顯著量想着它，所以我想」 d分享我想出的。這適用於32位機器上的整數。如果x是0或1，則返回x。

int ilog2(int x) { 

    int byte_count = 0; 
    int y = 0; 

    //Shift right 8 
    y = x>>0x8; 
    byte_count += ((!!y)<<3); 

    //Shift right 16 
    y = x>>0x10; 
    byte_count += ((!!y)<<3); 

    //Shift right 24 and mask to adjust for arithmetic shift 
    y = (x>>0x18)&0xff; 
    byte_count += ((!!y)<<3); 


    x = (x>>byte_count) & 0xff; 

    x = x>>1; 
    byte_count += !!x; 
    x = x>>1; 
    byte_count += !!x; 
    x = x>>1; 
    byte_count += !!x; 
    x = x>>1; 
    byte_count += !!x; 
    x = x>>1; 
    byte_count += !!x; 
    x = x>>1; 
    byte_count += !!x; 
    x = x>>1; 
    byte_count += !!x; 
    x = x>>1;   //8 
    byte_count += !!x; 


    return byte_count; 

}

來源

2014-10-02 05:23:32 swsmith

的問題是等於「找到的二進制數的1的最高位」

STEP 1：1的所有左邊設置爲1 像0x07000000到0x07ffffff

x = x | (x >> 1); 
x = x | (x >> 2); 
x = x | (x >> 4); 
x = x | (x >> 8); 
x = x | (x >> 16); // number of ops = 10

第2步：返回計數1名的字和減去1

參考數目：Hamming weight

// use bitCount 
int m1 = 0x55; // 01010101... 
m1 = (m1 << 8) + 0x55; 
m1 = (m1 << 8) + 0x55; 
m1 = (m1 << 8) + 0x55; 
int m2 = 0x33; // 00110011... 
m2 = (m2 << 8) + 0x33; 
m2 = (m2 << 8) + 0x33; 
m2 = (m2 << 8) + 0x33; 
int m3 = 0x0f; // 00001111... 
m3 = (m3 << 8) + 0x0f; 
m3 = (m3 << 8) + 0x0f; 
m3 = (m3 << 8) + 0x0f; 

x = x + (~((x>>1) & m1) + 1); // x - ((x>>1) & m1) 
x = (x & m2) + ((x >> 2) & m2); 
x = (x + (x >> 4)) & m3; 
// x = (x & m3) + ((x >> 4) & m3); 

x += x>>8; 
x += x>>16; 

int bitCount = x & 0x3f; // max 100,000(2) = 32(10) 
// Number of ops: 35 + 10 = 45 
return bitCount + ~0;

這就是我的做法。謝謝〜

來源

2017-03-04 02:48:40

2014年1月[barak manos]（http://stackoverflow.com/users/1382251/barak-manos）鏈接提供的相同功能的好解釋：[整數的aggregate.org/MAGIC/#Log2] （http://aggregate.org/MAGIC/#Log2%20of%20an%20Integer）和[aggregate.org/MAGIC/#Population Count（Ones Count）]（http://aggregate.org/MAGIC/#Population% 20Count％20％28Ones％20Count％29）。也感謝維基百科鏈接。 – olibre

僅使用C中的按位運算符來計算log_2（x）的底面

回答

相關問題