Мне нужно подсчитать количество единиц в двоичном представлении целого числа. Два требования:
1) Необходимо использовать поиск по таблице 2) Необходимо использовать побитовый оператор XOR
Пока, я думаю, у меня есть поиск по таблице, который сработает:
const generateLookupTable = (int) => {
const range = Array.from({length: int}, (x,i) => i);
const toBinary = (table, i) => {
const binary = (i >>> 0).toString(2);
table[i] = binary;
return table;
}
const lookupTable = range.reduce(toBinary, {})
return lookupTable;
};
Это напечатает что-то вроде:
generateLookupTable(7)
{0: "0", 1: "1", 2: "10", 3: "11", 4: "100", 5: "101", 6: "110"}
Я не понимаю, как использовать XOR для решения этой проблемы (или зачем мне вообще использовать таблицу поиска). Я чувствую, что могу легко решить эту проблему, преобразовав int в двоичный, а затем просто перебирая каждый символ и суммируя единицы, которые я вижу. Однако требования усложняют задачу.
Это похоже на проблему качества, которую дает хорошее образование.
const totallyUsed = {}[0^0];
, потом код. «Надо использовать» просто смешно, что считается «употреблением»? Если это какое-то полностью принудительное использование, которое не служит никакой другой цели, я думаю, что вышеупомянутое делает свою работу.
Возможный дубликат Эффективно подсчитывайте количество бит в целом числе в JavaScript
Это лишь частичный намек, но он был слишком длинным для комментария. Одна из вещей, которую вы можете сделать с помощью XOR, - это найти крайнюю правую единицу. Затем вы можете вычесть это и сделать это снова, сохраняя счет. Это скажет вам, сколько единиц в номере:
function countOnes(n) {
let count = 0
while(n > 0) {
n -= n ^ (n & (n -1))
count++
}
return count
}
let n = 1709891;
console.info(countOnes(n))
console.info(n.toString(2))
n = 7
console.info(countOnes(n))
console.info(n.toString(2))
n = 9
console.info(countOnes(n))
console.info(n.toString(2))
Может быть, это немного поможет. Не уверен, что на самом деле нужны инструкции.
похоже, это работает! не могли бы вы объяснить n -= n ^ (n & (n -1))
? я не понимаю 1) почему вы вычитаете из n 2) почему вы вычитаете 1 из n 3) что & и ^ делают в этом случае
Чтобы найти биты в числе, существует множество подходов - есть также подход макро-сжатой таблицы, но он не использует xor. Есть и другие, которые где-то в строке используют xor, но не нуждаются в таблице поиска. Можно, например, принудительно используйте xor в методе таблицы, но тогда это скорее шутка.
@Edmund, если вы хотите узнать больше о побитовых операциях в JavaScript, прочтите документацию по MDN. Также имейте в виду, что приведение чего-либо к строке происходит бесконечно медленнее, чем побитовая операция. developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
Если бы нужно было просто реализовать это без ограничений, используйте это: const countBits = n => { n = n - ((n >>> 1) & 0x55555555); n = (n & 0x33333333) + ((n >>> 2) & 0x33333333); return ((n + (n >>> 4) & 0xF0F0F0F) * 0x1010101) >>> 24; };
- см. graphics.stanford.edu/~seander/bithacks.html (Набор битов счета). Также обратите внимание, что WebAssembly предлагает доступ к инструкции SSE __popcnt
, но взаимодействие WebAssembly с Javascript всегда связано с большими накладными расходами, поэтому при использовании в основном в JS он не работает быстрее. Но речь идет не об этом, а о тех странных дополнениях, которые «надо использовать».
@Edmund ^
- это XOR, а &
- побитовое AND. Проще всего перебирать маленькие числа и следить за битами. Например, начиная с 6 110
&
5 101
дает вам 100
. XOR, который с 6 дает вам 10
или 4 самый правый бит. Теперь вычтите 4 из 6, что приведет к удалению самого правого бита, и делайте это снова, пока у вас не закончатся биты.
Этот n -= n ^ (n & (n -1))
можно было бы записать как n ^= n & -n
, немного проще, но все же использует XOR.
@ASDFGerte Этот код из C, который строго типизирован. В JS вы можете получить значительный прирост скорости, сначала приведя n к int32 перед первой операцией, то есть n => { n = (n|0) - ...
. Я тестировал здесь несколько вариантов: jsperf.com/fast-int32-bit-count
Не в первый раз к хорошему дизайну мешают требования.