c++ - 查找连续的 1 和 0

Question

我正在寻找将整数流转换为计算连续 1 和 0 的列表的最快方法。

例如整数[4294967295,4194303,3758096384]

位级:

11111111111111111111111111111111
11111111111111111111110000000000
00000000000000000000000000000111

(每一串位都是小端顺序)

所以程序应该输出三个值:[54 39 3] 有 54 个，然后是 39 个零，最后是 3 个。

我一直在研究这些算法: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear

可能我需要按照这些思路写点东西

i=(the first bit of the first integer)
repeat till the end
    find the number of consecutive i's in this integer
    if we reach the end of the integer, continue with the next
    else i = (not)i

但我想知道是否有人可以想出更好的方法。

目前函数是在 Matlab 中构建的，如下所示:

%get all bits in a long vector
data = uint32([4294967295,4194303,3758096384]);
logi = false([1,length(data)*32]);
for ct = 1:length(data)
    logi(1+32*(ct-1):ct*32)=bitget(data(1+(ct-1)),1:32);
end
%count consecutive 1s and 0s
Lct=1;
L=1;i = logi(1);
for ct = 2:length(logi)
    if logi(ct)==i
        L(Lct)=L(Lct)+1;
    else
        i=logi(ct);
        Lct=Lct+1;
        L(Lct)=1;
    end
end

>> L = 54    39     3

注意:我花了一些时间才把问题弄清楚。因此，有关语言和问题的确切性质的评论。希望(经过多次编辑后)这个问题现在以一种可以找到的形式出现，并且答案也对其他人有用。

Answer 1

之前我误解了这个问题。现在我知道你在问什么了。这应该有效，我已经测试过了:

#include <iostream>
#include <deque>

using namespace std;

//old version for whole collection
void ConsecutiveOnesAndZeros(deque<uint32_t> values, deque<uint8_t> &outCount)
{
    int i;
    if (!values.empty()) {
        uint8_t count = 0, lastBit = (values[0] & 1);
        for (uint32_t &value : values)
        {
            for (i = 0; (i < 32) && (value != 0); i++)
            {
                if (lastBit != uint8_t((value >> i) & 1))
                {
                    outCount.push_back(count);
                    count = 0;
                    lastBit = !lastBit;
                }
                count++;
            }
            if (i < 32) count += (32 - i);
        }
        outCount.push_back(count);
    }
}

//stream version for receiving integer
void ConsecutiveOnesAndZeros(uint32_t value, uint8_t &count, uint8_t &lastBit, deque<uint8_t> &outCount)
{
    int i;
    for (i = 0; (i < 32) && (value != 0); i++)
    {
        if (lastBit != uint8_t((value >> i) & 1))
        {
            if(count) outCount.push_back(count);
            count = 0;
            lastBit = !lastBit;
        }
        count++;
    }
    if (i < 32) count += (32 - i);
}

int main()
{
    deque<uint8_t> outCount;
    deque<uint32_t> stream = { 4294967295u,4194303u,3758096384u };

    ConsecutiveOnesAndZeros(stream, outCount);
    for (auto res : outCount) {
        printf_s("%d,", res);
    }
    printf_s("\n");

    uint8_t count = 0, bit = 0;
    outCount.clear();
    for (auto val : stream) 
        ConsecutiveOnesAndZeros(val, count, bit, outCount);
    if (count) outCount.push_back(count);

    for (auto res : outCount) {
        printf_s("%d,", res);
    }
    printf_s("\n");

    system("pause");
}

更新 - 我对检查值做了一些优化!= 0。我还将 ConsecutiveOnesAndZeros 分为两个函数，用于从接收到的流中给出下一个整数。