Find repeating bit sequence in number-CodePudding

How can I find multiples of a given bit sequence? So the code should work like this:

int bit = 0b100

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

This should print 4 (100) and 36 (100100). I was trying to iterate through it and bit-mask it but it also printed numbers like 40 (101000).

So it should only print numbers containing only multiplies of that sequence (100, 100100, 100100100 ...) but not numbers like 1100, 1001001 ...

CodePudding user response：

You can use the modulo operator and shift operator to check the lower bits of the number and "reduce" the incoming number to check the next lower bits of the remaining number. The algorithm works like this:

Do a modulo of the sequence on the number to check. The modulo must be 0.

So when you have the sequence 0b100 and you have a number to check like 0bXXXXXXXX101 the modulo would be 0b001, which is not 0 and you know the number can't be a sequence of multiple 0b100s.

Shift the remaining number to the right, since you have already checked the first N bits on the right.

You shift the number with the >> operator. This will move the bits to the right, dropping the already checked bits:

0bXXXXXXXX101
   0bXXXXXXXX   (shifted to the right)

The tricky part is to calculate how big the shift is. You can use log2() to figure that out. When you completed the shift, you go back to point 1 above.

The complete code can look like this:

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);
}

When you try it with the following code:

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));

You will get the following output:

true
true
true
false
false
true
false

You might need to check for negative inputs as this method only works for positive numbers.

CodePudding user response：

I'm not sure how to do it with pure math, but regex works:

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);
    }
}

Edit: What about going the other direction?

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

CodePudding user response：

As @user16320675 pointed out, it would be more efficient to just generate those numbers (instead of searching them in a continuous range of integers).

This can be achieved shifting (to left) and OR'ing until the width of the bit pattern exceeds the bit length of an integer.

For example:

int b = 0b100; // the pattern
// Compute r as the bit length of pattern b  
int r = Integer.SIZE - Integer.numberOfLeadingZeros(b); 

int x = b; // start with b
int i = r; // i is the length occupied until now
while (i <= Integer.SIZE) {
    System.err.println(x);
    i  = r; 
    x <<= r;
    x |= b;
}