只用位運算實現比較兩整數大小,有沒有簡短優雅的O(1)的解法?
聽說這是某軟的一道面試題.只用位運算,不用四則運算以及比較運算符比較兩個無符號整數的大小。那麼有沒有優雅簡短而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=0A&這完全與指令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 RETCMP_BY_BIT ENDP;調用上述函數:
INVOKE CMP_BY_BIT,73543,73544
JE EQUAL JA GREATERTHAN JB LESSTHANEQUAL:
;若相等則跳轉到這裡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),但如果是後者,由於數據長度都不固定,不可能存在常數演算法。
這個
diff = numa ^ numb
然後,你們就看 @夏洋的答案吧。
編程之美有一道求二進位中1的個數,和這個類似。要想做到,只有一個最暴力的方法。打個所有數據的表,不過針對無符號整數這個有
種排列,同時你題目也要求了不能用比較語句。
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編程語言 |