Check integer is bit rotation of another integer

Question

Given two integers a and b, how can we check that b is a rotated version of a?

For example if I have a = 0x01020304 (in binary 0000 0001 0000 0010 0000 0011 0000 0100), then the following b values are correct:

...
0x4080C1 (right-rotated by 2)
0x810182 (right-rotated by 1)
0x2040608 (left-rotated by 1)
0x4080C10 (left-rotated by 2)
...

I wonder if there is any solution, other than actually rotating the original value and check for a match. :/ — Peter Jaloveczki, Jun 07 '13 at 08:43
Just 32 times loop (32 bit in your case) and check for a match. — Boris, Jun 07 '13 at 08:45
I have no idea how much this would help speed things up, but you could try and use the [POPCNT compiler intrinsic](http://msdn.microsoft.com/en-us/library/bb385231(v=vs.90).aspx) to count the _number of bits_ of `a` and `b`, respectively. If the numbers differ, the answer must be `false`. Otherwise you do the full check for all possible rotations. — jogojapan, Jun 07 '13 at 09:01
This is hard because rotation is not a mathematical operation, unlike shift (which is a multiply or divide by power of two) — MSalters, Jun 07 '13 at 10:54
I'm still waiting for someone to post an answer based on polynomial division :) — avakar, Jun 07 '13 at 13:06
pop count might be an usefull optimization if cpu implements that instruction, aka break immediately if number of ones in 2 numbers dont match — NoSenseEtAl, Jun 07 '13 at 13:19

score 6 · Answer 1 · answered Jun 07 '13 at 11:36

6

For n bit numbers you can use KMP algorithm to search b inside two copies of a with complexity O(n).

answered Jun 07 '13 at 11:36

Quimey

153
1
10

MSalters · Accepted Answer · 2013-06-09T00:15:31.180

5

In C++, without string conversion and assuming 32 bits int:

void test(unsigned a, unsigned b)
{
  unsigned long long aa = a | ((unsigned long long)a<<32);
  while(aa>=b)
  {
    if (unsigned(aa) == b) return true;
    aa>>=1;
  }
return false;
}

edited Jun 09 '13 at 00:15

answered Jun 07 '13 at 10:58

MSalters

173,980
10
155
350

1

It seems this one is the best answer. A little update to include b in the parameter. Thanks – Jun 08 '13 at 00:59
Just some small notes: (1) It should rather be `unsigned long long`, shouldn't it? (2) The type of a shift expression is that of the left operand, so you should rather cast the `a` in there to `unsigned long long`, just using `32LL` is not enough. – Christian Rau Jun 08 '13 at 14:10
You can eventually test if(unsigned(aa)==a) return false; because of symetry, some numbers have less than 32 different rotations, like 0xAAAAAAAA, though I don't know if it will statistically fast up or slow down – aka.nice Jun 09 '13 at 23:06
1

Or just do {...} while( unsigned(aa)!=a); it will iterate 32 times at most, sometimes less. – aka.nice Jun 09 '13 at 23:23

WoJo · Answer 3 · 2013-06-07T09:03:23.897

4

i think you have to do it in a loop (c++):

// rotate function
inline int rot(int x, int rot) {
   return (x >> rot) | (x << sizeof(int)*8 - rot));
}

int a = 0x01020304;
int b = 0x4080C1;
bool result = false;

for( int i=0; i < sizeof(int)*8 && !result; i++) if(a == rot(b,i)) result = true;

edited Jun 07 '13 at 09:03

answered Jun 07 '13 at 08:48

WoJo

360
2
10

Doesn't work for the same a and b. You should start loop from i=0. – Boris Jun 07 '13 at 08:58
3

Fist of all I'd rather use `unsigned int`s for any reasonable bit manipulation, then `CHAR_BIT` would be a bit better fit than `8` (or just `std::numeric_limits::digits` instead of the whole `sizeof` madness), but Ok, those are just minor flaws. In general this is probably the best approach still. – Christian Rau Jun 07 '13 at 09:14

Oliver Charlesworth · Answer 4 · 2013-06-07T09:10:46.333

3

In the general case (assuming arbitrary-length integers), the naive solution of consisting each rotation is O(n^2).

But what you're effectively doing is a correlation. And you can do a correlation in O(n log n) time by going via the frequency domain using an FFT.

This won't help much for length-32 integers though.

edited Jun 07 '13 at 09:10

answered Jun 07 '13 at 09:01

Oliver Charlesworth

267,707
33
569
680

That sounds interesting. Could you be more specific?? – Sungmin Jun 07 '13 at 10:39
It's wrong, though: considering each rotation is only O(N). You rotate a to match b, but b itself isn't rotated. – MSalters Jun 07 '13 at 11:00
@MSalters: There are O(N) rotations and comparisons, but each comparison is also O(N). – Oliver Charlesworth Jun 07 '13 at 11:11
3

I think this is one of the cases where talking about complexity is useless. If the question was about BigIntegers I would side with you. However in this case the CPU doesn't compare bit by bit so the O(N^2) seems a bit misleading to me. – Honza Brabec Jun 07 '13 at 14:45
@HonzaBrabec: I see what you mean, but the reason I posted this general response is because the OP specifically said "integers" rather than "`ints`"; I may have been reading too much into that though... – Oliver Charlesworth Jun 07 '13 at 14:49

score 1 · Answer 5 · edited May 23 '17 at 12:18

1

By deriving the answers here, the following method (written in C#, but shall be similar in Java) shall do the checking:

public static int checkBitRotation(int a, int b) {
    string strA = Convert.ToString(a, 2).PadLeft(32, '0');
    string strB = Convert.ToString(b, 2).PadLeft(32, '0');
    return (strA + strA).IndexOf(strB);
}

If the return value is -1, b is not rotated version of a. Otherwise, b is rotated version of a.

edited May 23 '17 at 12:18

Community

1
1

answered Jun 07 '13 at 08:59

David

3,957
2
28
52

5

Meh, before converting the whole thing into strings and doing a string search, I'd rather execute that simple integer bit shift loop 32 times. – Christian Rau Jun 07 '13 at 09:10
2

+1 for a neat trick I wouldn't have thought of. Probably slower than just brute forcing it, but still neat. – Retired Ninja Jun 07 '13 at 09:18
you can use `std::bitset<32>::to_string()`, not much to it. – TemplateRex Jun 07 '13 at 09:54

score 1 · Answer 6 · answered Jun 07 '13 at 22:14

If a or b is a constant (or loop-constant), you can precompute all rotations and sort them, and then do a binary search with the one that isn't a constant as key. That's fewer steps, but the steps are slower in practice (binary search is commonly implemented with a badly-predicted branch), so it might not be better.

In the case that it's really a constant, not a loop-constant, there are some more tricks:

if a is 0 or -1, it's trivial
if a has only 1 bit set, you can do the test like b != 0 && (b & (b - 1)) == 0
if a has 2 bits set, you can do the test like ror(b, tzcnt(b)) == ror(a, tzcnt(a))

if a has only one contiguous group of set bits, you can use

int x = ror(b, tzcnt(b));
int y = ror(x, tzcnt(~x));
const int a1 = ror(a, tzcnt(a));     // probably won't compile
const int a2 = ror(a1, tzcnt(~a1));  // but you get the idea
return y == a2;

if many rotations of a are the same, you may be able to use that to skip certain rotations instead of testing them all, for example if a == 0xAAAAAAAA, the test can be b == a || (b << 1) == a
you can compare to the smallest and biggest rotations of the constant for a quick pre-test, in addition to the popcnt test.

Of course, as I said in the beginning, none of this applies when a and b are both variables.

Evgeniy Dorofeev · Answer 7 · 2013-06-07T09:40:08.630

0

I would use Integer.rotateLeft or rotateRight func

static boolean isRotation(int a, int b) {
    for(int i = 0; i < 32; i++) {
        if (Integer.rotateLeft(a, i) == b) {
            return true;
        }
    }
    return false;
}

edited Jun 07 '13 at 09:40

answered Jun 07 '13 at 08:48

Evgeniy Dorofeev

133,369
30
199
275

1

You're only doing 30 tests out of the 32 possible values. While it's arguable whether `x == y` means no rotation, you're still missing at least one case. – syam Jun 07 '13 at 08:53
well, on the other hand then b is not a rotated version of a – Evgeniy Dorofeev Jun 07 '13 at 08:55
Which is why I said it was arguable. But you **still** miss the 31th rotation, even if you consider the 0th (aka. 32th) rotation should return false. – syam Jun 07 '13 at 09:10
I agree, that's a bug, fixed – Evgeniy Dorofeev Jun 07 '13 at 09:14
input is a and b, but you check x and y? – David Jun 07 '13 at 09:23
I mean isRotation(int a, int b) vs (Integer.rotateLeft(x, i) == y) – David Jun 07 '13 at 09:32

Check integer is bit rotation of another integer

7 Answers7