Найти следующий номер с конкретным весом Хэмминга

Question

Учитывая определенное целое число x, я хочу вычислить следующее более высокое целое число y, которое имеет определенный вес Хэмминга w. Имейте в виду, что вес Хэмминга х не должен быть также w.

Так, например, x = 10 (1010) и w = 4, результат должен быть y = 15 (1111).

Очевидно, я мог бы добиться этого, просто увеличивая x, но это было бы очень медленным решением для больших чисел. Можно ли как-то добиться этого с помощью битовых сдвигов?

Answer 1

Есть три случая: вес Хэмминга (он же битовый подсчет населения) уменьшается, не изменяется или увеличивается.

Увеличенный вес Хэмминга

Установите достаточно последовательных младших битов 0 для достижения желаемого веса.

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

Неизменный вес Хэмминга

1. Добавьте значение младшего бита 1-го порядка.
2. При необходимости увеличьте вес Хэмминга, как указано выше.

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

Пока сложение "несет единицу", биты будут очищены. Полученный вес должен быть равным или уменьшенным. Если несколько битов очищены из-за цепочки переносов, вам нужно увеличить вес компенсации, установив младшие биты.

Уменьшенный вес Хэмминга

1. Достаточно убрать 1 младший бит младшего разряда, чтобы достичь нового желаемого веса.
2. Следуйте вышеописанному процессу для неизменного веса.

Это работает, потому что очистка 1-битов младшего разряда находит предыдущее число с желаемым весом, вычитая наименьшее жизнеспособное количество. Из предыдущего номера правильного веса следуйте алгоритму "неизменный вес", чтобы достичь следующего числа.