Подсчет несимметричных байтов - PullRequest
4 голосов
/ 07 ноября 2010

Я ищу чистый способ перечисления (8-битных) целых чисел, двоичное представление которых не совпадает с другим целым числом вплоть до поворота и отражения.

Например, список, вероятно, начнется как
0
1
(2 = 10b пропущено, потому что вы можете вращать биты в 1, поэтому все степени 2 пропускаются. Также каждое число, кроме 0, будет нечетным)
3 = 11b
5 = 101b 7 = 111b
9 = 1001b 11 = 1011b (поэтому 13 = 1101b будет пропущено, поскольку 11010000b является отражением 1101b, которое затем можно повернуть вправо 4 раза) .
.
,

Также, в идеале, как это можно обобщить на числа с разным количеством битов (16, 32 или просто n ) и другие основания помимо 2.

Ответы [ 4 ]

1 голос
/ 07 ноября 2010

Поскольку @Джон Смит считал, что мой комментарий является хорошим ответом, здесь он является ответом.

Ответы здесь могут быть осветительными.

0 голосов
/ 07 ноября 2010

Вы можете использовать сито, похожее на сито Эратосфена для простых чисел.

Используйте битовый массив (BitSet в Java) с одним битом для каждого числа.

Изначально пометить все биты.

Пройдите последовательно через битовый массив, пока не найдете следующий бит с индексом n, это число в вашем наборе. Затем очистите биты всех других чисел, которые могут быть достигнуты с n с помощью вращения и зеркального отображения.

На современных машинах это возможно до 32 бит, которые будут использовать 512 МБ памяти.

0 голосов
/ 07 ноября 2010

Альтернативным решением для Решета Эратосфена было бы создать тест T (k), который возвращает True или False для любого заданного k.

Это было бы медленнее, но в этом случае хранилище не понадобилось бы,таким образом, он будет легче распространяться на произвольную длину данных.

Если вы на мгновение упростите задачу и скажете, что мы просто пытаемся отбросить отражения, это будет легко:

T_ref(k) returns true iff k <= Reflection(k).

Что касается вращающихся битов, то можно сделать то же самое:

T_rot(k) returns true iff k == MIN{the set of all rotations of k}

Можно подумать о делении целых чисел на группу классов эквивалентности E (k), где E (k) - множество всехперестановки отражения и вращения k.

Возможно, вы захотите потратить немного времени, чтобы убедиться, что множество натуральных чисел N легко разбивается на такие непересекающиеся подмножества.

Тогда множество

{k s.t. k == MIN(E(k)) } 

гарантирует, что в каждом классе эквивалентности будет содержаться ровно один элемент.

Это будет действительно хороший вопрос для интервью.

0 голосов
/ 07 ноября 2010

Спасибо Джеффроми за лучшее объяснение проблемы - я удалил свой предыдущий ответ.

Вот еще одно решение в Perl. Perl - хороший язык для такого рода проблем, поскольку он позволяет легко воспринимать числа как текст, а текст как числа.

i: for $i (0..255) {
  $n1 = sprintf "%08b", $i;    # binary representation of $i

  $n2 = $n1;                   # "unreflected" copy of $n1
  $n3 = reverse $n1;           # "reflection" of $n1 

  for $j (1..8) {
    $n2 = chop($n2) . $n2;     # "rotate" $n2
    $n3 = chop($n3) . $n3;     # "rotate" $n3
    next i if $found{$n2} or $found{$n3};
  }

  # if we get here, we rotated $n2 and $n3 8 times
  # and didn't get a nonsymmetric byte that we've
  # seen before -- this is a nonsymmetric byte
  $found{$n1}++;
  print "$i   $n1\n";
}

Это не так просто, как в предыдущем решении, но задача состоит в том, чтобы попробовать все 16 комбинаций (2 отражения x 8 поворотов) и сравнить их со всеми несимметричными байтами, которые вы видели ранее.

В Perl есть оператор для сдвига битов с вращением, но использованная мной идиома chop($num) . $num лучше обобщает проблемы с базой n .

...