只用位運算實現比較兩整數大小，有沒有簡短優雅的O(1)的解法？

01-04

聽說這是某軟的一道面試題.只用位運算，不用四則運算以及比較運算符比較兩個無符號整數的大小。那麼有沒有優雅簡短而O(1)的演算法呢？

改了一下 @夏洋的代碼，避免了 if (!diff) ...; 及 x ? a : b 這些比較和分支。

#define POPULATE_RIGHT(X) X |= X &>&> 1; X |= X &>&> 2; X |= X &>&> 4; X |= X &>&> 8; X |= X &>&> 16


#define REPLICATE_LSB(X)

    X |= X &<&< 1;
    X |= X &<&< 2;
    X |= X &<&< 4;
    X |= X &<&< 8;
    X |= X &<&< 16

#define SELECT(COND, A, B) ((COND)  (A)) | (~(COND)  (B))

int compare(uint32_t a, uint32_t b) {
  uint32_t diff = a ^ b;  
  POPULATE_RIGHT(diff);

  uint32_t greater = a  (diff ^ (diff &>&> 1));

  POPULATE_RIGHT(greater);

  REPLICATE_LSB(greater);
  uint32_t non_zero = diff  1;

  REPLICATE_LSB(non_zero);

return SELECT(non_zero, SELECT(greater, 1, -1), 0); }

這樣應該更符合題目要求。

用位操作做比較的意義不大，但使用 SELECT() 這種方式去避免分支，在 SIMD 編程中是很常用的技巧。

嚴格來說這不是O(1)而是O(logL)。

int compare(uint32_t a, uint32_t b) { uint32_t diff = a ^ b; if (!diff) return 0;


  // 001xxxxx -&> 00100000

  diff |= diff &>&> 1;

  diff |= diff &>&> 2;

  diff |= diff &>&> 4;

  diff |= diff &>&> 8;

  diff |= diff &>&> 16;

  diff ^= diff &>&> 1;

return a diff ? 1 : -1; }

講道理unsigned int的長度是常數。。

這就是要設計一個數字比較器電路啊，只用基本邏輯門的似乎只有樹型串聯，延遲是O(log2(N))，並聯也做不到O(1)。放個八位的感受下。

int cmp(unsigned int a, unsigned int b) // a&>b?1:0 { #define _M (1 &<&< 31) return (a^b) !(((a_M) ^ (b_M)) (b_M)) (((a_M) ^ (b_M) a_M) || cmp(a&<&<1, b&<&<1)); #undef _M }

利用遞歸與短路求和進行逐位判斷

考慮到高級語言(即使是C)的位運算功能被嚴重閹割，我們就寫彙編吧。

思路：對於兩個unsigned int型變數A，B，分情況討論：

(1) 若A==B，則二者異或運算後結果一定為0；

(2) 若A&>B，則從高位向低位數起，二者第一次出現不同的二進位位時，A在該位處的值一定為1，B在該位處的值一定為0

(3)若A&

問題是如何找到A，B從高位數起的第一個不同的二進位位？答案還是異或運算，A與B求異或存入寄存器EAX中。用位查找BSR指令查找EAX從高位起的第一個1的位置：有以下幾種情況：

(1)若沒有找到，則ZF被設置為1，說明A異或B==0，即A==B

(2)若找到了，該位置對應的就是A和B從高位數起第一個1，即為A和B的第一個不同的位置，再用BT指令將B的該位存入CF標誌位，若B的該位為0，則CF=0，A&>B，反之若B的該位為1，CF=1，A&

如此一番折騰後，我們發現CF和ZF標誌會被設置如下：

A==B：ZF=1，CF未知

A&>B ：ZF=0，CF=0

A&這完全與指令CMP A,B後的結果相同(實際上並不能這麼寫指令，因為A,B全是內存變數，只是打個比方)，也就是說，這麼操作的效果和CMP A,B後的結果完全相同，可以用JA,JB,JE進行比較結果跳轉。

-------------------------------------------------------
代碼：(386以上保護模式彙編)
;比較函數（改變了寄存器EAX，若需要保護EAX請在調用前備份）：
CMP_BY_BIT PROC,A:DWORD,B:DWORD
MOV EAX,A
XOR EAX,B
BSR EAX,EAX
BT B,EAX
RET
CMP_BY_BIT ENDP

;調用上述函數：
INVOKE CMP_BY_BIT,73543,73544
JE EQUAL
JA GREATERTHAN
JB LESSTHAN
EQUAL:
;若相等則跳轉到這裡
GREATERTHAN:
;若大於則跳轉到這裡
LESSTHAN:

;若小於則跳轉到這裡
以上

這個問題本質上相當於求MSB
可MSB也只能做到O(log n)，如夏洋的答案
如果可以用其他位運算指令的話（題目說不能用CMP比較運算符）。。。所有支持O(1)計算MSB的硬體都可以做到
比如ARM, X86, MIPS都是支持CLZ指令的（Count Leading Zeros），等於變相支持算MSB
但估計在面試領域這應該就不是位運算的範疇了……
_______________________________________
王軒的答案里用的是BSR位操作符，和CLZ基本上是同樣的功能，只不過BSR的適用範圍更窄，只有x86架構支持，而CLZ基本上是業界標準，常用的ARM，X86，MIPS架構都會支持，IBM/Oracle的伺服器架構也支持，建議用CLZ會更好一點
另外，如果想用assembly里的位操作指令，不需要全部使用assembly語言，只需要在C裡面調用_asm_宏就可以了（depends on compiler also）

——————————————————————
另補充說明：如果像Felix Qiu的答案里用數字電路比較器，這些屬於組合邏輯（combinational logic），如果邏輯層數不多，比如32bit或者64bit，是全部可以在一個cycle之內完成的
事實上如果用assembly的CMP指令，在硬體內部就是這麼implement然後一個cycle搞定的

沒一個人答在點子上。
O(1)就是常數次的操作。
大O表示法表示的是漸進時間複雜度啊。
「時間複雜度常用大O符號表述，不包括這個函數的低階項和首項係數。使用這種方式時，時間複雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況。」

對於unsigned int，是可以想辦法打表的

用電路做，以32位數為例，一共是二乘二的32次方個點，a數接通一個觸點，b數接通另一個觸點，測量兩個點的電勢或電流方向，O1複雜度。
改進一下，以32位數為例，共64個觸點，一邊32個，接通為1，斷開為0，然後做異或後測量哪一側電位高

如果把整數以二進位表示，其實就是比較兩個二進位數的大小，位運算的左右移動相當於乘除法，奇偶測試就是看某一位是0是1，這很容易給出O（1）解

不清楚你說的無符號整數，是系統中已經存在的數據結構呢，還是自建的數據結構。如果是前者，因為數據結構長度固定，那麼肯定存在常數演算法O（1），但如果是後者，由於數據長度都不固定，不可能存在常數演算法。

這個 $O(1)$ 定義有點奇葩，無符號整數是定長的4個位元組，所以勉強可以成為 $O(1)$ ，不過如果題目給出一個大整數，那麼幾乎不可能做到 $O(1)$
思路如下：
明顯有： $sum_{ k=1 }^{ N- 1}2^k<2^N$
則只需要找出第一個從最高位開始找出第一個不同的Bit
diff = numa ^ numb
然後，你們就看 @夏洋的答案吧。
編程之美有一道求二進位中1的個數，和這個類似。要想做到 $O(1)$ ，只有一個最暴力的方法。打個所有數據的表，不過針對無符號整數這個有 $2^{32}$ 種排列，同時你題目也要求了不能用比較語句。
所以，以上都是廢話。

1. 增加一位符號位

2. 取異或
3. 判斷符號位
4. 不會寫代碼
5. O(1) 是攤還成本嗎？

額，一個數大小為n，位數就是log n，你要比較大小必然要比較log n次。
所以O(1)的演算法存在么……

位移也算位運算的。
兩個數字相減然後右移（原來的位數﹣1）位。
得到1表示結果是負的，得到0表示結果是正的。
然後套一個四則式就出來較大或者較小的一個了，你隨意。

比如返回較大的一個，偽代碼
uint16 Max(uint16 a, uint16 b)
{
int32 minus = (int32)a - (int32)b;
int32 result = minus &>&> 31;
return a*(1-result) + b*resu<
}
當然，return這句話也可以再寫成位運算，自己搞搞就是了。

#include "stdafx.h"
int main() { unsigned int in_1 = 0, in_2 = 0; unsigned int temp = 0; unsigned int bit = 0x80000000; scanf("%u %u", in_1, in_2); temp = in_1^in_2; while (!(bittemp)) { bit = bit &>&> 1; } temp = in_1bit ? in_1 : in_2; printf(" %u ", temp); return 0; }

可以賦值么……可以的話先O(L)求出兩個數的最高比另一個數大的位數，然後打表判斷…由於L是常數所以O(1)

return (a^b)0x80000000;

public int getMax(int a, int b)
{
int a1 = (a - b &>&> 31) + 1;
int b1 = (b - a &>&> 31) + 1;
int[] ii = new int[2];
ii[a1] = a;
ii[b1] = b;
return ii[1];
}
來自一個Csharp菜逼；

推薦閱讀：

※什麼是deformation quantization？
※請問σ-代數（sigma-algebra）的含義是什麼，能否舉例說明？
※在以前沒有計算器的年代，開根號是怎麼做到的？
※如何用向量（a，b，c）和（x，y，z）表示向量（ax，by，cz）？
※目前數學有沒有結構比較清晰嚴謹的基礎部分？

TAG:微軟Microsoft | 演算法 | 數學 | 編程 | C編程語言 |