计数字节数组中的尾随零位

Question

指定了3个字节的数组。将其视为24位数组，请计算一个之后的零个数。 （{00000100，00000011，00001000}-对于此数组，答案为2。）我的代码给出1，但它不正确，如何解决？

#include <iostream>
#include <bitset>
using namespace std;

int main() {
    int res = 0, res1 = 0;
    _int8 arr[3] = { 4, 3, 8 };
__asm {
    mov ecx, 3 
    mov esi, 0
    start_outer:
        mov bx, 8 
        mov al, arr[esi]
    start_inner :
        shl al, 1 
        jnb zero 
        jc one 
    one :
        dec bx к
        test bx, bx
        jnz start_inner 
        jmp end_ 
    zero :
        dec bx 
        test bx, bx
        jz end_
        inc res 
        shl al, 1 
        jnb was_zero 
        jc start_inner 
    was_zero :
        dec bx 
        dec res 
        jmp start_inner 
    end_ :
        inc esi
        loop start_outer
}
cout << res << endl;
system("pause");
}

Answer 1

[基本上，用户@Michael已经给出了正确的答案。因此，所有功劳归于他。

在堆栈溢出时，您可以在此处找到很多摆弄的帖子。但是，您可以在“ Henry S. Warren，Jr.”]的《 [[“ Hacker's Delight”]中找到有关此类活动的很好描述。我在这里有第二版。 解决方案在第2章中介绍，

“基本”

，然后“ 2-1操纵最右边的位”如果手动检查，

NOT

可以满足您的条件，那么您会发现这些值是0,1,3,7,15,31,63,127,255，

或二进制

0b0000'0000，0b0000'0001，0b0000'0011，0b0000'0111，0b0000'1111，0b0001'1111，0b0011'1111，0b0111'1111，0b1111'1111，

并且我们检测到这些值对应于2 ^ n-1。并且，根据

“ Hacker's Delight”

，我们可以使用简单的公式求出(x & (x + 1)) != 0

因此，我们可以将其翻译为以下代码：

#include <iostream>

int main() {
    unsigned char arr[3];

    unsigned int x, y, z;
    std::cin >> x >> y >> z;

    arr[0] = static_cast<unsigned char>(x);
    arr[1] = static_cast<unsigned char>(y);
    arr[2] = static_cast<unsigned char>(z);

    unsigned char res = ((arr[0] & (arr[0] + 1)) != 0) +  ((arr[1] & (arr[1] + 1)) != 0) + ((arr[2] & (arr[2] + 1)) != 0);

    std::cout << static_cast<unsigned int>(res) << '\n';
    return 0;
}

非常重要。您不需要汇编代码。优化编译器几乎总是会胜过您的手写代码。

您可以在Compiler Explorer上检查许多不同的版本。在这里您可以看到，带有静态值的代码示例将被完全优化。编译器将简单地计算编译时间，并简单地将2显示为结果。所以，请注意。编译器资源管理器将向您显示由不同的编译器针对所选硬件生成的汇编语言。如果需要，可以接受。

请另外注意：以上草绘的算法不需要任何分支。除非您要遍历数组/向量。为此，您可以编写一个小的lambda并使用C ++标准库中的算法。

C ++解决方案

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>

int main() {

    // Define Lambda to check conditions
    auto add = [](const size_t& sum, const unsigned char& x) -> size_t {
        return sum + static_cast<size_t>(((x & (x + 1)) == 0) ? 0U : 1U); };

    // Vector with any number of test values
    std::vector<unsigned char> test{ 4, 3, 8 };

    // Calculate and show result
    std::cout << std::accumulate(test.begin(), test.end(), 0U, add) << '\n';

    return 0;
}