计算存在有效 0 位的数组元素（低于最高 1 位）

Question

指定了一个 3 字节的数组。计算任何一个之后有零的字节数。即，最高位 1 以下的位不全是 1.

{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 章中提出，"Basics"，然后是 "2–1 Manipulating Rightmost Bits"

如果你手动检查，哪些值不满足你的条件，那么你会发现这些是

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, [=14]

并且我们检测到这些值对应于 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 作为结果。所以，警告。 Compiler explorer 将向您显示由不同编译器和针对选定硬件生成的汇编语言。如果你愿意，你可以接受。

另外请注意：上面的草图算法不需要任何分支。除非，如果你想遍历 array/vector。为此，您可以编写一个小的 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;
}

Answer 2

下次试试

下次请尽量解释清楚。很多人不明白你的问题。反正。我希望我现在明白了。

我会解释一个字节使用的算法。在程序的后面，我们将运行简单的外循环 3 次，以处理所有值。而且，我当然会在汇编程序中显示结果。而且，这是许多可能的解决方案之一。

我们可以观察到以下情况：你的声明 "Count the number of bytes where there's a zeros after any one." 意味着你想计算一个字节中一位从 1 到 0 的转换次数。而且，如果我们查看从 msb 到 lsb 的位。所以，从左到右。

如果我们反之亦然，那么如果我们从右到左，我们也可以计算从 0 到 1 的转换次数。

从 0 到 1 的转换始终可以通过 "and" 将新值与旧值取反来计算。示例：

OldValue NewValue NotOldValue And
       0 0        1           0
       0 1        1           1   --> Rising edge
       1 0        0           0
       1 1        0           0

我们也可以说，如果没有设置旧的，以前的值，而设置了新值，那么我们就有了上升沿。

如果我们将字节右移，我们可以一个接一个地查看（一个字节的）一位。然后，新值（新的最低位）将是 LSB。我们记得以前的旧位，然后进行测试。然后我们设置 old = new，再次读取新值，进行测试等等。我们对所有位都这样做。

在 C++ 中，这可能如下所示：

#include <iostream>
#include <bitset>

using byte = unsigned char;

byte countForByte(byte b) {
    // Initialize counter variable to 0
    byte counter{};

    // Get the first old value. The lowest bit of the orignal array entry
    byte oldValue = b & 1;

    // Check all 8 bits
    for (int i=0; i<8; ++i) {

        // Calculate a new value. First shift to right
        b = b >> 1;

        // Then mask out lowest bit
        byte newValue = b & 1;

        // Now apply our algorithm. The result will always be 0 or one. Add to result
        counter += (newValue & !oldValue);

        // The next old value is the current value from this time
        oldValue = newValue;
    } 
    return counter;
}

int main() {
    unsigned int x;
    std::cin >> x;
    std::cout << std::bitset<8>(x).to_string() << "\n";
    byte s = countForByte(x);
    std::cout << static_cast<int>(s) << '\n';
    return 0;
}

因此，无论出于何种原因，您都需要一个汇编程序解决方案。同样在这里，您需要告诉人们您为什么想要它，您使用什么编译器以及您使用什么目标微处理器。不然怎么会有人给出正确答案呢？

无论如何。这里是X86架构的解决方案。使用 MS VS2019 测试。

#include <iostream>

int main() {
    int res = 0;
    unsigned char arr[3] = { 139, 139, 139 };

    __asm {
            mov esi, 0;         index in array
            mov ecx, 3;         We will work with 3 array values
DoArray:
            mov ah, arr[esi];   Load array value at index
            mov bl, ah;         Old Value
            and bl, 1;          Get lowest bit of old value

            push ecx;           Save loop Counter for outer loop
            mov ecx, 7;         7Loop runs to get the result for one byte
DoTest:
            shr ah, 1;          This was the original given byte
            mov al, ah;         Get the lowest bit from the new shifted value
            and al, 1;          This is now new value
            not bl;             Invert the old value
            and bl, al;         Check for rising edge
            movzx edi, bl
            add res, edi;       Calculate new result
            mov bl, al;         Old value = new value
            loop DoTest

            inc esi;            Next index in array
            pop ecx;            Get outer loop counter

            loop DoArray;       Outer loop
    }
    std::cout << res << '\n';
    return 0;
}

对于这项工作，我想要 100 个赞成票和一个被接受的答案。 . .

计算存在有效 0 位的数组元素（低于最高 1 位）

Count array elements where there are significant 0 bits (below the highest 1 bit)

c++

x86

assembly

masm

visual-c++