无符号多头序列计数常见位 [英] Counting common bits in a sequence of unsigned longs

问题描述

我要寻找比下面更快的算法如下。定的64位无符号整数的顺序，返回各六十四比特被序列中设定的次数的计数。

例如：

  4608 = 0000000000000000000000000000000000000000000000000001001000000000
4097 = 0000000000000000000000000000000000000000000000000001000000000001
2048 = 0000000000000000000000000000000000000000000000000000100000000000计数0000000000000000000000000000000000000000000000000002101000000001
 

例如：

  2560 = 0000000000000000000000000000000000000000000000000000101000000000
530 = 0000000000000000000000000000000000000000000000000000001000010010
512 = 0000000000000000000000000000000000000000000000000000001000000000计数0000000000000000000000000000000000000000000000000000103000010010
 

目前我使用的是相当明显的，幼稚的做法：

 静态INT位= sizeof的（ULONG）* 8;公共静态INT [] CommonBits（PARAMS ULONG []值）{
    INT [] =计数新INT [比特]
    INT长度= values​​.Length;    的for（int i = 0; I＆LT;长度;我++）{
        ULONG值=值[I]
        对于（INT J = 0; J＆LT;比特放大器;＆放大器;值= 0;！J ++，值=价值＆GT;＆GT; 1）{
            计数[J] + =（INT）（价值和放大器; 1UL）;
        }
    }    返回计数;
}
 

解决方案

一个小的速度改善可能通过先中用OR整数在一起，然后用结果来确定哪些位，你需要检查来实现。你还是将不得不遍历每个位，但只有一次在那里有没有1秒，而不是 values​​.Length 次位。

I am looking for a faster algorithm than the below for the following. Given a sequence of 64-bit unsigned integers, return a count of the number of times each of the sixty-four bits is set in the sequence.

Example:

4608 = 0000000000000000000000000000000000000000000000000001001000000000 
4097 = 0000000000000000000000000000000000000000000000000001000000000001
2048 = 0000000000000000000000000000000000000000000000000000100000000000

counts 0000000000000000000000000000000000000000000000000002101000000001

Example:

2560 = 0000000000000000000000000000000000000000000000000000101000000000
530  = 0000000000000000000000000000000000000000000000000000001000010010
512  = 0000000000000000000000000000000000000000000000000000001000000000

counts 0000000000000000000000000000000000000000000000000000103000010010

Currently I am using a rather obvious and naive approach:

static int bits = sizeof(ulong) * 8;

public static int[] CommonBits(params ulong[] values) {
    int[] counts = new int[bits];
    int length = values.Length;

    for (int i = 0; i < length; i++) {
        ulong value = values[i];
        for (int j = 0; j < bits && value != 0; j++, value = value >> 1) {
            counts[j] += (int)(value & 1UL);
        }
    }

    return counts;
}

解决方案

A small speed improvement might be achieved by first OR'ing the integers together, then using the result to determine which bits you need to check. You would still have to iterate over each bit, but only once over bits where there are no 1s, rather than values.Length times.

这篇关于无符号多头序列计数常见位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！