Добавление битов в той же позиции (или ранг или уровень) в массиве чисел - PullRequest
Новая
       2

Добавление битов в той же позиции (или ранг или уровень) в массиве чисел

2 голосов
/ 28 февраля 2012

В поисках лучшего алгоритмического подхода к моей проблеме.Любое понимание этого очень ценится.

У меня есть массив чисел, скажем, 

short arr[] = [16, 24, 24, 29]; 
// the binary representation of this would be [10000, 11000, 11000, 11101]

Мне нужно добавить бит в позиции 0 каждого числа и бит в позиции 1 каждого числа и так далее ... сохранить егов массиве, поэтому мой выходной массив должен выглядеть следующим образом: 

short addedBitPositions = [4, 3, 1, 0, 1]; 
// 4 1s in leftmost position, 3 1s in letmost-1 position ... etc.

Решение, которое я могу думать, таково: 

addedBitPosition[0] = (2 pow 4) & arr[0] + (2 pow 4) & arr[1] + 
                      (2 pow 4) & arr[2] + (2 pow 4) & arr[3];

addedBitPosition[1] = (2 pow 3) & arr[0] + (2 pow 3) & arr[1] + 
                      (2 pow 3) & arr[2] + (2 pow 3) & arr[3];

... so on

Если длина arr [] возрастает до Mи число битов в каждом M [i] увеличивается до N, тогда временная сложность этого решения составляет O (M * N).

Могу ли я сделать лучше?Спасибо!

1 Ответ

0 голосов
/ 28 февраля 2012

Вы можете попытаться замаскировать каждое число масками 0b100...100...100...1 с единицами в каждой позиции k. Затем сложите замаскированные числа вместе - вы получите суммы битов в позициях 0, k, 2k ... Повторите это с маской, сдвинутой влево на 1, 2, ..., (k-1), чтобы получить суммы для других битов , Конечно, для извлечения сумм требуется еще немного взлома. Кроме того, k должен быть выбран так, чтобы 2 ** k < M (длина массива), чтобы избежать переполнения.

Я не уверен, что это действительно того стоит, но может быть для очень длинных массивов и N > log₂ M.

EDIT

На самом деле, N > log₂ M не является строгим требованием. Вы можете сделать это для «достаточно маленьких» кусочков всего массива, а затем сложить вместе извлеченные значения (это O (M)). В бит-хакинге фактическое big-O часто затмевается постоянным фактором, поэтому вам нужно поэкспериментировать, чтобы выбрать лучший k и размер фрагмента массива (при условии, что этот метод дает какое-либо улучшение по сравнению с простым суммированием, которое вы описали конечно).

...