在数字中查找重复的位序列

Question

如何找到给定位序列的倍数？所以代码应该像这样工作：

int bit = 0b100

for (int i = 0; i<=50;i++){
     if (bit in i){
         print(i);
     }
}

这应该打印 4 (100) 和 36 (100100)。我试图遍历它并对其进行位掩码，但它也打印了像 40 (101000) 这样的数字。

因此它应该只打印仅包含该序列（100、100100、100100100 ...）的倍数的数字，而不是像 1100、1001001 ...

这样的数字

Answer 1

我不确定如何用纯数学来做，但正则表达式有效：

Pattern pattern = Pattern.compile("^(100)+$");
    
for (int i = 0; i < 100; i++) {
    String binary = Integer.toBinaryString(i);
    if (pattern.matcher(binary).find()) {
        System.out.println(i + " " + binary);
    }
}

编辑：换个方向怎么样？

StringBuilder builder = new StringBuilder();
for (int i = 0; i < 10; i++) {
    builder.append("100");
    System.out.println(Integer.parseInt(builder.toString(), 2));
}

Answer 2

您可以使用模运算符和移位运算符来检查数字的低位，并“减少”传入数字以检查剩余数字的下一个低位。该算法的工作原理如下：

对要检查的数字序列取模。模数必须为 0.

所以当你有序列 0b100 并且你有一个数字要检查时 0bXXXXXXXX101 模数将是 0b001，而不是 0 你知道数字不能是多个 0b100 的序列。

将剩余的数字向右移动，因为您已经检查了右边的前 N 位。

您使用 >> 运算符移动数字。这会将位向右移动，丢弃已经检查的位：

0bXXXXXXXX101
   0bXXXXXXXX   (shifted to the right)

棘手的部分是计算偏移量。您可以使用 log2() 来计算。完成轮班后，您返回上面的第 1 点。

完整的代码如下所示：

public static boolean isMultipleOfSequence(int sequence, int number) {
    if (sequence == 0) {
        return number == 0;
    }
    while (number != 0) {
        int remaining = number % sequence;
        if (remaining != 0) {
            return false;
        }
        int shift = log2(sequence);
        number = number >> shift;
    }
    return true;
}

public static int log2(int value) {
    return Integer.SIZE-Integer.numberOfLeadingZeros(value);
}

当您使用以下代码尝试时：

System.out.println(isMultipleOfSequence(0b100, 0b100));
System.out.println(isMultipleOfSequence(0b100, 0b100100));
System.out.println(isMultipleOfSequence(0b100, 0b100100100));
System.out.println(isMultipleOfSequence(0b100, 0b101100100));
System.out.println(isMultipleOfSequence(0b100, 0b100110100));
System.out.println(isMultipleOfSequence(0b101, 0b101101101));
System.out.println(isMultipleOfSequence(0b101, 0b100101101));

您将得到以下输出：

true
true
true
false
false
true
false

您可能需要检查负数输入，因为此方法仅适用于正数。

在数字中查找重复的位序列

Find repeating bit sequence in number

java

bit