Я на самом деле сделал это, используя небольшую ловкость рук: одной справочной таблицы с 16 записями будет достаточно, и все, что вам нужно сделать, это разбить двоичный повтор на кусочки (4-битные кортежи).Сложность на самом деле O (1), и я написал шаблон C ++, который специализировался на размере целого числа, которое вы хотели (в # битах) ... делает его константным выражением вместо неопределенного.
Между прочим, вы можетеиспользуйте тот факт, что (i & -i) вернет вам однобитный LS и просто зациклите, удаляя lsbit каждый раз, пока целое число не станет равным нулю - но это старый трюк контроля четности.