每12位Python的Python計數數爲1

Question

我有60位的二進制數，並且想要計算每12位中1的＃號。

輸入是64位數字，我放棄最重要的4位保留60位。然後，計算60位中1的＃號。

目前，我有漢明重量（https://en.wikipedia.org/wiki/Hamming_weight）的表示形式，它確實以60位返回1的＃號。但是，我想將它擴展到每個x位，x將是一個參數。

會有人分享想法如何實現它嗎？

def hamming_weight(y): 
    x = y & 0xFFFFFFFFFFFFFFF 

    x -= (x >> 1) & 0x5555555555555555 
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333) 
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    return ((x * 0x0101010101010101) & 0xffffffffffffffff) >> 56 

Answer 1

這是一個使用的解決方案。我在那裏留下了一些調試打印，以顯示它的工作原理。它取任何整數，該整數中的字節數（用於填充目的），以及所需的組大小。請注意，最後一個組可能包含少於group_size數字。

import itertools 

# https://docs.python.org/3/library/itertools.html#itertools-recipes 
def grouper(n, iterable, fillvalue=None): 
    "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx" 
    args = [iter(iterable)] * n 
    return itertools.zip_longest(fillvalue=fillvalue, *args) 


def count_ones(num, total_bits, group_size): 
    # Turn the original number to a string of ones and zeros 
    num_bin_str = bin(num)[2:] 

    # That discards any zeros that are supposed to be on the left 
    # so pad it with those if necessary 
    padded_bin_str = '0' * (total_bits - len(num_bin_str)) + num_bin_str 
    print(padded_bin_str) 

    for g in grouper(group_size, padded_bin_str, 0): 
     print(g) 
     yield sum(map(int, filter(None, g))) 


for i in count_ones(0b10011, 8, 2): 
    print(i) 

了許多0b10011的輸出，是真正爲兩個組大小的8位號碼：

00010011 
('0', '0') 
0 
('0', '1') 
1 
('0', '0') 
0 
('1', '1') 
2 

以下是我認爲這將有一個64位數字的工作要砍下60位和計數1的

# So, starting with a 64 bit integer (I'm just picking one at random here) 
# make sure that the number isn't bigger than 64 bits, otherwise I'm not sure if the following trick will work 
import random 
n = random.randint(0, 2**64 - 1) 
# change the first 4 bits to 0 so they don't screw every thing up 
# basically I want to generate 64 bits of 1's, 
# discard the leftmost 4, and & it with n 
# check this- not sure it's 100% correct 
n &= ((2**64 - 1) >> 4) 

# Now, I should have a large number, but the first ones are 0s 

for ones in count_ones(n, 60, 8): 
    print(ones) 

和輸出是：

000000001011001000010110010000101100100001011001000010110010 
('0', '0', '0', '0', '0', '0', '0', '0') 
0 
('1', '0', '1', '1', '0', '0', '1', '0') 
4 
('0', '0', '0', '1', '0', '1', '1', '0') 
3 
('0', '1', '0', '0', '0', '0', '1', '0') 
2 
('1', '1', '0', '0', '1', '0', '0', '0') 
3 
('0', '1', '0', '1', '1', '0', '0', '1') 
4 
('0', '0', '0', '0', '1', '0', '1', '1') 
3 
('0', '0', '1', '0', 0, 0, 0, 0) 
1 # Note that we ran out of bits before group size so it's filling it with zeros 

Answer 2

我相信，如果你的分額是整除您的總位數這將工作：

bits = str(x) 
#number of ranges to check... your example would be 60/12=5 
for i in range(len(bits)/splitNum):      
    sum=0  
    #number of characters to check for '1'...your example would be indexes[0,12),[12,24)...[48,60)     
    for j in range(i*splitNum, i*splitNum + splitNum): 
     if bits[j] == '1': 
      sum+=1 
    print(sum) #could also add to a list here, etc 

或者更簡單：

bits = str(x) 
sum = 0 
for i in range(len(bits)): 
    if bits[i] == '1': 
     sum+=1 
    if i % splitNum == 0: 
     print(sum) #or something else 
     sum = 0 

我希望這些概念解決或至少讓你走上了解決問題的正確道路：D

Answer 3

bitmath技術可以適應12位塊的水平求和，但要在塊的大小上進行通用化並不容易。對於兩種尺寸的功率來說很容易，通常它可以完成，但不容易。假設焦點是12位塊，那麼可以像這樣得出它。

• 12是由2整除，所以使相鄰的成對的總和是細（在這個意義上，它從未總結「橫跨」的組塊邊界），則5..步驟可以留下。現在問題變成了「6個數據塊中的2位數字的水平和」。
• 6仍然可以被2整除，所以做小數小數也好，3..步可以留下。
• 3不能被2整除，但3很小，只是做一個3部分的總和。

在第二步中我們得到的半字節中，每個半字節都是它的位。所以它們的寬度是4位，但最大值是4.在原地添加3個（沒有提前空間）仍然有效，最大值只有12位，沒有進入下一個半字節。所以，同樣的技術可以使用，但總結3個啃並用不同的面膜：

x = (x + (x >> 4) + (x >> 8)) & 0xf00f00f00f00f00f 

其實頂部f不需要在你的情況，也許不需要，如果你離開它，你含蓄做計數爲60位（不必明確屏蔽掉4個最高位）。一般來說，它會在那裏。

在總（未測試）

def hamming_weight(y): 
    x = y & 0xFFFFFFFFFFFFFFF 

    x -= (x >> 1) & 0x5555555555555555 
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333) 
    return (x + (x >> 4) + (x >> 8)) & 0xf00f00f00f00f00f 

您可以從建築看它爲什麼不推廣好，塊大小的大素因子不會分解這整齊。它仍然可以完成，但是您必須使用額外的遮罩來避免在塊邊界之間進行求和，並且您會遇到一些不合理的子場大小的煩人情況。計算必要的掩碼並不容易，在運行時可能不值得。例如，對於7塊大小，你可以這樣做（未測試）

# sums of adjacent bits, with extra bit summed into the top 
x = (x & 0x952a54a952a54a95) + ((x & 0x2a54a952a54a952a) >> 1) + ((x & 0x4081020408102040) >> 2) 
# sums of 3-in-a-row nibs, since there are only 3 left per chunk anyway 
x = (x & 0x83060c183060c183) + ((x & 0x0c183060c183060c) >> 2) + ((x & 0x3060c183060c1830) >> 4) 

..這也許可以簡化一些。