回答
假設我們有N位的數量x
。你可以這樣寫:
b(N-1) b(N-2) b(N-3) ... b(0)
其中b(i)
是在數位號i
(其中0是最顯著位)。
x/2
相同x
左移1個比特。我們假設無符號數字。所以:
x/2 = 0 b(N-1) b(N-2) ... b(1)
現在我們XOR x
與x/2
:
x^(x/2) = b(N-1)^0 b(N-2)^b(N-1) b(N-3)^b(N-2) ... b(0)^b(1)
注意,這個最右邊位(最顯著位)爲b(N-1)^0
這是b(N-1)
。換句話說,你可以從結果中立即得到b(N-1)
。當你有這個位時,你可以計算出b(N-2)
,因爲結果的第二位是b(N-2)^b(N-1)
,你已經知道了b(N-1)
。依此類推,您可以計算原始數字x
的所有位b(N-1)
至b(0)
。
我可以給你在比特的算法:
假設你有n比特的數組:
b = [b1 .. bn] // b1-bn are 0 or 1
原始陣列是:
x0 = b0
x1 = b1^x0
x2 = b2^x1
或一般
x[i] = b[i]^x[i-1]
Assum E Y = X ^(X/2)
如果你想找到X,這樣做
X = 0
do
X ^= Y
Y /= 2
while Y != 0
我希望它能幫助!
我知道這是一個老話題,但我偶然發現了同樣的問題,我發現了一個小竅門。如果你有ň位,而不需要ň位操作(如由加斯帕的答案),你可以用的log 2(N)數操作做到這一點,:
假設y是等於x XOR(x/2)在程序開始時,您可以執行以下C程序:
INPUT : y
int i, x;
x = y;
for (i = 1; i < n; i <<= 1)
x ^= x >> i;
OUTPUT : x
在這裏您可以找到解決方案。
- 「>>」是正確的位移操作。例如,二進制數13,1101(如果右移1)將變爲二進制110,因此13 >> 1 = 6. x >> i相當於x/2^i(在整數中除法,當然)
- 「< <」 是左移位操作(ⅰ< < = 1相當於I * = 2)
爲什麼它的工作?讓我們以如實施例N = 5比特,並且其中y = B4 B3 B2 B1 B0(二進制:在下面的x被寫入二進制也,但我被寫入十進制)開始
- 初始化:
X = B4 B3 B2 B1 B0
- 第一步:I = 1
X >> 1 = B4 B3 B2 B1所以我們有 X = B4 B3 B2 B1 B0 XOR B3 B2 B1 B0 = B4(B3^B4)(B2^B3)(B1^B2)(B 0^B1)
- 第二步驟中:i = 2
x >> 2 >> b4(b3^b4)(b2^b3)所以我們有 x = b4(b3^b4)(b2^b3)(b1^b2)(b0^b1)XOR b4(b3^b4) (B2^B3)= B4(B3^B4)(B2^B3^B4)(B1^B2^B3^B4)(B0^B1^B2^B3)
- 第三步:i = 4的
x >> 4 = b4所以我們有 x = b4(b3^b4)(b2^b3^b4)(b1^b2^b3^b4)(b0^b1^b2^b3)XOR b4 = b4(b3^B4)(B2^B3^B4)(B1^B2^B3^B4)(B0^B1^B2^B3^B4)
- 然後I = 8,這是超過5個,我們退出循環。
而且我們有所需的輸出。
循環有log2(n)次迭代,因爲我從1開始,在每一步乘以2,所以爲了達到n,我們必須做log2(n)次。
- 1. 簡化Z = X ^(X << Y)函數的逆函數
- 2. x = pow(y,5)是什麼反函數
- 3. CRYSTAL REPORT什麼是x:= x;?
- 4. 是什麼X ++和++ X
- 5. 什麼是var x = x || {};
- 6. 什麼是{$ x}?
- 7. 成本函數,sum(x)和ones(1,length(x))* x之間的區別是什麼?
- 8. 逆轉位的整數x
- 9. 總和數u和列表x u + x1 + x2的方案函數
- 10. C:int x = k *(x1,x2,x3)?
- 11. 爲什麼x ++ - + - ++ x合法但是x +++ - +++ x不是?
- 12. 什麼是list.count(x => x * x> 1)在做什麼?
- 13. 會是什麼.SelectMany(X => X)是SQL
- 14. python中itertools.izip的逆函數是什麼?
- 15. (ctypes.c_int * len(x))(* x)是做什麼的?
- 16. x = x ++;的影響是什麼?
- 17. x的值是什麼? X = A ++ + ++ A + A ++
- 18. 什麼是「x && foo()」?
- 19. x = x ++ + ++ x的評估順序是什麼?是?
- 20. 「if(x){...}」是什麼意思?其中x是C++中的整數?
- 21. 爲什麼存在x ++和++ x,x + = 2但不是x = + 2?
- 22. 爲什麼x ** 3比x * x * x慢?
- 23. ''x''不是函數
- 24. 什麼是qsort void * x和*(int *)x?
- 25. 「declare + x」是什麼意思vs「declare -x」?
- 26. 什麼時候是(true == x)=== !! x false?
- 27. (x:_)和[x:_]是什麼意思?
- 28. (x << 13)^ x是什麼意思?
- 29. 什麼是+ X在表達式$ {GC_TUNE + X}
- 30. x的價值是什麼?
C還是Python?但是你可能想嘗試更多的數學方法,比如楓樹或matlab ......否則它會很難 – ThiefMaster 2012-03-08 12:38:56
這兩種語言的表達式都是一樣的 - 沒關係。 – fadedbee 2012-03-08 12:43:00
啊,我以爲你想計算一個任意函數的反轉 – ThiefMaster 2012-03-08 12:48:05