找出最长的 1 和 0 交替串

Question

我正在学习汇编中的位运算。从位运算的角度来说，找到最长的0 或1 串很靠前，但是怎么找到最长的1 和0 交替串。

我认为它与前两个类似，因为您只需要右移并进行适当的操作，然后重复直到全为 0，但我想不通出解决方案。有什么想法吗？

谢谢！

编辑

一些例子： 101101010001 有一串 6 个交替出现的 1 和 0。数字 1010 有一个字符串 4 个连续的 1 和 0。我真的不关心 0 和 1 的交替字符串，所以 0101 只是 2，因为它中间有 10

我使用的架构是ARM A9处理器

这是我试过的

.text
.global _start
_start:

MOV R5, #0//Store final result
MOV R6, #0
MOV R2 , #0
MOV R7, #0
LDR R3 , =TEST_NUM

ONES: LDR R1, [R3]  //Load the data word into R1 
    MOV R0, #0      // R0 will hold the result
LOOP: CMP R1, #0     //loop until data contains no more ones
    BEQ NEXT
    LSR R2, R1, #1  //Perform shift, followed by and
    XOR R1, R1, R2
    ADD R0, #1      // count number of iterations
    B LOOP
NEXT: CMP R5, R0 //
    MOVLE  R5, R0
    B END
END:   B END

TEST_NUM: .word 0x1fffffff, 0x7fffffff
.end

Answer 1

这是您可以用来获取最长交替位模式的逻辑：

int last_bit = num & 1;
int count = 1;
int bit_at_pos;    //holds LSB
num = num >> 1;
int longest = 1;

while(num > 0){
    bit_at_pos = num & 1;
    if(bit_at_pos == 1 - last_bit){  //Checks if this bit is alternate to last bit or not.
        count++;    
    }else{
        if(longest < count) longest = count;
        count = 1;
    }
    last_bit = bit_at_pos;
    num = num >> 1;
}
// longest is the answer

Answer 2

如果您已经有了计算连续 1 的数量的算法，那么您可以转换输入，使交替模式中的每个位都设置为 1，然后将其输入到 1s-计数算法。

假设交替模式必须以 1 开头，如果它是 1 后跟 0 或 0 前跟 1，您想要设置一个位，如下所示：

x = (x & ~(x << 1)) | (~x & (x >> 1))

然后统计x中连续1的个数

找出最长的 1 和 0 交替串

Find longest alternating string of 1's and 0's

algorithm

bit-manipulation

bitwise-operators