按位操作邏輯任務

我已經在這個問題上思考了很多個小時，但解決方案並不想來。也許有人有任何想法？按位操作邏輯任務

的問題是：

"Using ONLY bitwise operators, write the function that sets 
    the leftmost zero bit to one" 

Conditions - prohibited 
Recursion - prohibited 
Loops - prohibited 
Arithmetic operations - prohibited

實施例：

輸入：11010010

輸出：11110010

P.S.輸入實際上應該是無符號整型，但爲了簡單起見，讓它成爲二進制，它僅僅是細節。

來源

2013-07-27 Ikakok

您可以將最左邊的零傳播到右是這樣的：

x &= x >> 1; 
x &= x >> 2; 
x &= x >> 4; 
// etc

在這個例子中，你會得到1100萬

然後，如果你顛倒，你得到那些面具達並且包括最左邊的零，在這個例子中，00111111

然後，可以分離出最左邊的一個（其中，構造，是在相同的位置在輸入最左邊的零），因爲容易與x^(x >> 1)

只是進入輸入。

將其組合在一起：（未測試）

uint32_t y = x; 
x &= x >> 1; 
x &= x >> 2; 
x &= x >> 4; 
x &= x >> 8; 
x &= x >> 16; 
x = ~x; 
return y | (x^(x >> 1));

有可能是一個簡單的解決方案

來源

2013-07-27 12:09:50 harold

一段時間後，來到了類似的解決方案爲harold建議，但有一些改進。下面是代碼

unsigned long int getLastZeroPosition(unsigned long int value) 
{ 
    unsigned long int temp = ~value; 
    temp = temp | temp >> 1; 
    temp = temp | temp >> 2; 
    temp = temp | temp >> 4; 
    temp = temp | temp >> 8; 
    temp = temp | temp >> 16; 
    temp = temp | temp >> (sizeof(unsigned long int) << 2); // handles x86/x64 

    temp = temp >> 1; 
    temp = (~temp) & (~value); 
    return temp; 
}

來源

2013-07-31 08:35:14 Ikakok

無需臨時| =臨時>> 64，因爲該行之前，我已經換了31（1 + 2 + 4 + 8 + 16）。所以在32位的情況下已經足夠了，其他的轉換都不會起作用。但是，如果它是x64，那麼它將另外移位32（sizeof（ui）<< 2 = 8 << 2 = 32）。總而言之，它將改變爲63。 – Ikakok

我會認爲我可以實現使用Java。如果更改問題「只用按位運算符，編寫設置最右邊零位到一個功能」，那麼你可以如下解決這個問題：

int a = 0b1111_1111_1111_1111_1111_1101_0110_1111; 
a = a | (a & (a^(a+1)))+1; 
System.out.println(Integer.toBinaryString(a));

這個答案是我們所需的鏡子，所以乾脆先鏡像輸入：

int a = 0b1111_1111_1111_1111_1111_1101_0110_1111; 
a = Integer.reverse(a); 
a = Integer.reverse(a | (a & (a^(a + 1))) + 1); 
System.out.println(Integer.toBinaryString(a));

但當然，使用一個Java的內置（reverse），使您能夠使用其他的權利（highestOneBit）太：

int a = 0b1111_1111_1111_1111_1111_1101_0110_1111; 
a = Integer.highestOneBit(~a)+a; 
System.out.println(Integer.toBinaryString(a));

如果你想使用基本的位運算符來實現自己的reverse，並在C可能實現，這也是可能的：Reverse bits

來源

2015-04-24 01:02:26 YoYo

按位操作邏輯任務

回答

相關問題