位計數

我得到了在採訪中以下問題plz幫助我一些想法解決它作爲我完全不知道如何着手位計數

n個元素的非空數組A包含八進制表示的非負整數K，即A的每個元素屬於區間[0; 7]

寫功能：

int bitcount_in_big_octal(const vector<int> &A);

返回在K的二進制表示設置爲1的位的函數應該返回-1，如果比特設置爲1的數目超過10,000,000的數量。

假設數組可能非常大。

假設N是範圍[1..100,000]內的整數。

是Java嗎？ :) –

你到目前爲止嘗試過什麼？而且，這是一個C++函數原型，而不是Java。 –

有沒有時間限制？我有一個想法：首先，製作下面的字典，{0-> 0,1-> 1，2-> 1,3-> 2,4-> 1,5-1> 6-> 2， 7-> 3}。然後循環數組A以使用字典在每個元素中對1進行求和。

2011-12-10 15:32:32 meteorgan

遍歷您表示
的for-each在迭代元素的表示轉換成其位數。 @ meteorgan的答案是做這件事的好方法。如果你需要表示除了位數以外的東西，你可能想把它轉換成一些中間形式，對你將要使用的任何東西有用 - 例如到byte[]：表示中的每個八位組都應該對應一個單獨的byte，並且由於您所做的只是計算位數，所以Java的字節是否被簽名並不重要。然後，每個陣列中byte，使用現有的位計數lib，施放byte到int和使用Integer.bitCount(...)，或推出自己的，等等 - 數位
結果添加到正在運行總，逃脫如果你達到你的門檻，迭代。

這是一個詳細的Java答案（就像我鏈接的lib），但算法步驟對C++來說很好，找到替代庫（或使用字典答案）。

2011-12-10 15:37:01 Carl

Thx傢伙我會嘗試。 –

下面是使用基於索引（字典）的方法的解決方案。

INDEX = [0, 1, 1, 2, 1, 2, 2, 3] 

def bitcount_in_big_octal(A): 
    counter = 0 
    for octal in A: counter += INDEX[octal] 
    return counter

2013-03-26 11:39:19 joamag

回答