Проверка целых чисел - это чередование бит другого целого числа

Ответ 1

В С++ без преобразования строк и предполагая 32 бита 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;
}

Ответ 2

Для n разрядных номеров вы можете использовать алгоритм KMP для поиска b внутри двух копий со сложностью O (n).

Ответ 3

Я думаю, вам нужно сделать это в цикле (С++):

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

Ответ 4

В общем случае (предполагая произвольные целые числа) наивное решение, состоящее из каждого вращения, равно O (n ^ 2).

Но то, что вы эффективно делаете, - это корреляция. И вы можете сделать корреляцию в O (n log n) времени проходящей через частотный домен, используя FFT.

Однако это не поможет для целых чисел длиной 32.

Ответ 5

Получив ответы здесь, следующий метод (написанный на С#, но должен быть похож на Java) должен выполнить проверку:

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

Если возвращаемое значение равно -1, b не является повернутой версией a. В противном случае b - это версия версии.

Ответ 6

Я использовал бы Integer.rotateLeft или 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;
}

Ответ 7

Если a или b является константой (или константой цикла), вы можете предварительно скопировать все вращения и отсортировать их, а затем выполнить двоичный поиск с константой, которая не является константой. Это меньше шагов, но шаги на практике медленнее (двоичный поиск обычно реализуется с плохо спрогнозированной ветвью), поэтому может быть не лучше.

В случае, если он действительно является константой, а не константой цикла, есть еще несколько трюков:

• if a равно 0 или -1, это тривиально
• Если a имеет только 1 бит, вы можете выполнить тест, например b != 0 && (b & (b - 1)) == 0
• Если a установлено 2 бита, вы можете выполнить тест как ror(b, tzcnt(b)) == ror(a, tzcnt(a))

• если a имеет только одну непрерывную группу битов набора, вы можете использовать

  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;
  

• если много оборотов a совпадают, вы можете использовать это, чтобы пропустить определенные вращения вместо проверки их всех, например, если a == 0xAAAAAAAA, тест может быть b == a || (b << 1) == a
• вы можете сравнить с наименьшим и самым большим поворотом константы для быстрого предварительного тестирования в дополнение к тесту popcnt.

Конечно, как я сказал в начале, ни одно из этого не применяется, когда a и b являются обеими переменными.