Test if bits repeat in a number

Question

I'm looping over all length i bitstrings and was wondering how to tell if it is a repetition of a previous bitstring? Basically I want to skip 11, 1010, 1111, 0101, 101101 etc but not 1011, 1100, 1000, 101001 etc

These bit-strings are the periods of binary numbers so if they repeat it generates the same number which will throw off my data processing program.

The repeating sequences need to be adjacent and cover all of j without overflow

 skip = false; for(int i = 1; i<=n/2 && !skip; i++){ if(n%i == 0){ skip = true; for(int k=1; k<=n/i; k++) { if(((j&(j >> (i*k)))&((1<<i) - 1)) != (j&((1<<i) - 1))){ skip = false; break; } } } } if(skip) continue;

This is my current attempt but it seems to fail to detect any.

n is the length of the bit-string in bits

j is the bit-string

EDIT: Fixed a few typing errors, but now it detects 10 but not 11

still don't know what this means: "repetition of a previous bitstring" — Ben
– Ben, Commented Aug 11, 2014 at 19:42
skip == true; does nothing. The if(skip) continue; outside of the loop does nothing and you pulled the variable j out of seemingly nowhere. We need a bit more information here about what you're trying to do and what j and i are. — scohe001
– scohe001, Commented Aug 11, 2014 at 19:44
If it repeats inside of it, so if it is equal to some other bit-string repeated multiple-times inside of it.(ex 1010 is 10 repeated twice) — ruler501
– ruler501, Commented Aug 11, 2014 at 19:44
Seems clear to me, so don't go voting "unclear". Just read better. — user555045
– user555045, Commented Aug 11, 2014 at 19:52

anatolyg · Accepted Answer · 2014-08-11 20:17:56Z

You can do what you want in a completely different way.

Look at decimal numbers to reduce confusion. For example, the number 4545 is a repetition of the number 45. To detect this, you can divide by 101, and see that the result is less than 100.

In c++:

if (j % 101 == 0 && j / 101 < 100)

Now replace base 10 by base 2:

if (j % 5 == 0 && j / 5 < 4)

What if number of digits is not 2 but n?

Replace 4 by 1 << n
Replace 5 by (1 << n) + 1

What if you want to check repetition of 3 bit-strings? I am not sure you want it, but it seems possible.

Edit: I am too lazy to develop all the details, but consider the following hints:

Detect repetition of 3 patterns, 4 digits in each: divide by 100010001
100010001 = 999999999999 / 9999 (in decimal notation)
It's easy to figure out the general formula for what to divide by
To calculate a power of 10, you could use pow; fortunately, you actually need powers of 2 instead, so use 1 << whatever to raise 2 to whatever power

I need to check the repetition of i bit-strings for all i<n
So if I understand it right then the code for it would be if(j*((1<<i)-1) % ((1<<n)-1) == 0) skip = true;

Jarod42 · Accepted Answer · 2014-08-11 20:36:14Z

The pattern of the repetition may appears only a size which is a divisor of n.

So for n even, it is simple, just check both half bit to see if they are identical

bool does_bits_repeat(int n, unsigned b) { if (n % 2 == 0) { const unsigned high = b >> (n / 2); // (high & b) is equivalent to (high & low) return (high & b) == high; } else { // ... } }

The odd part is more tricky. you have to found the divisors d of n and with k from

unsigned k = 1; for (int i = 0; i != n; i += d) { k = k << d | 1; } // for n == 15, we have // d == 1, k = binary 111111111111111 (1 repeated 15 times) // d == 3, k = binary 001001001001001 (001 repeated 5 times) // d == 5, k = binary 000010000100001 (00001 repeated 3 times)

test if j is divisible by k.

Collectives™ on Stack Overflow

Test if bits repeat in a number

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related