爪哇 - 位操作（算上個1號）

-2

有人能解釋我爲什麼這種方法可行，我已經通過它做什麼工作，但爲什麼這項工作。有二進制數字的模式嗎？例如像在I = 3，爲什麼它做RES [1] + 1得到2，如何RES [3 >> 1] +（3 & 1）幫助數在3二進制數一的數量？爪哇 - 位操作（算上個1號）

代碼應該做什麼：它的工作原理，所以不用擔心。它應該返回一個列表，其中包含每個數字的二進制表示中的數字，直到num + 1。並且num始終> = 0。所以對於num = 5，您將得到[0,1,1,2,1,2]，其中最後一個索引表示二進制表示中的1的數目爲5，並且第一個指數是那些在二進制代表數0

代碼：

public int[] countBits(int num) { 
     int[] res = new int[num+1]; 

     for (int i = 0; i<num+1; i++){ 
      res[i] = res[i >> 1] + (i & 1); 
     } 

     return res; 
    }

這是一部分，我不能換我的頭周圍：

res[i] = res[i >> 1] + (i & 1);

編輯 - 這不是家庭主婦k，所以請充分解釋您的答案。這是爲了幫助採訪。

來源

2017-07-03 Theo

在我們試圖找出它「起作用」的原因之前，你能解釋一下它應該做什麼嗎？即'countBits（10）'（例如）應該是什麼結果？ – ajb

*有沒有二進制數字有的模式？* **是！** –

@ajb啊對不起，我應該提到的是，返回一個包含數字0到num數目的列表。所以在你的情況下，0到10包括在內。 – Theo

在

'RES [I] = RES [I >> 1] +（I & 1）;'

一個號碼的結果是分成2份

最後位是1或不是，這可通過（i & 1）來計算。
第一（N-1）個比特，這個數目等於RES [I >> 1]的bitcount.this是一個簡單的遞歸調用

來源

2017-07-03 00:58:51 Mosliu

int[] res = new int[num+1]; 

    for (int i = 0; i<num+1; i++){ 
     res[i] = res[i >> 1] + (i & 1); 
    } 

    return res;

改寫爲

int[] res = new int[num+1]; 

    for (int i = 0; i<num+1; i++){ 
     x = res[i >> 1]; 
     y = (i & 1); 
     res[i] = x + y; 
    } 

    return res;

創建一個數組以適應答案+1？

每個，開始在低端。

res[0] = res[0] + 0&1 = 0 + 0 = 0; 
res[1] = res[0] + 1&1 = 0 + 1 = 1; 
res[2] = res[1] + 0&1 = 1 + 0 = 0; 
res[3] = res[1] + 1&1 = 1 + 1 = 2;

望着這個模式，我可以看到，因爲右移，並與&掩蔽的，它的分裂問題爲2，一個一直因迭代順序之前解決，有些檢查最後一位數字。

假設一個8位的int，爲了簡潔，

1 = 00000001 
2 = 00000010 
3 = 00000011

分割二進制成零件。

i i>>1  y&1 
1 = 0000000  1 
2 = 0000001  0 
3 = 0000001  1

因此，它獲取數組前半部分的結果數，然後計算最後一位數。

由於迭代順序的，並且陣列初始化值，這是保證工作。

對於值< 0，由於2的補它變得發毛，這也就是爲什麼它僅適用於值> = 0

來源

2017-07-03 02:22:37

由1移位給出了2.
AND 1除以樓層數如果數字的最後一位是1，則返回1

希望下表有助於瞭解發生了什麼:)僅僅是我的2美分。

<pre> 
-------------------------------- 
<b> 
# 8 4 2 1 >>1 &1 Ans 
</b> 
------------------------------- 
0 0 0 0 0 0 0 0 
1 0 0 0 1 0 1 1 
2 0 0 1 0 1 0 1 
3 0 0 1 1 1 1 2 
4 0 1 0 0 2 0 1 
5 0 1 0 1 2 1 2 
6 0 1 1 0 3 0 2 
7 0 1 1 1 3 1 3 
8 1 0 0 0 4 0 1 
9 1 0 0 1 4 1 2 
10 1 0 1 0 5 0 2 
11 1 0 1 1 5 1 3 
12 1 1 0 0 6 0 2 
13 1 1 0 1 6 1 3 
14 1 1 1 0 7 0 3 
15 1 1 1 1 7 1 4 
</pre>

來源

2017-07-03 02:44:58 Vinay

爪哇 - 位操作（算上個1號）

回答

相關問題