Как подсчитать единицы в двоичном формате с помощью поиска по таблице и XOR?

Мне нужно подсчитать количество единиц в двоичном представлении целого числа. Два требования:

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 в двоичный, а затем просто перебирая каждый символ и суммируя единицы, которые я вижу. Однако требования усложняют задачу.

Не в первый раз к хорошему дизайну мешают требования.

ggorlen 01.08.2018 23:07

Это похоже на проблему качества, которую дает хорошее образование.

zfrisch 01.08.2018 23:19
const totallyUsed = {}[0^0];, потом код. «Надо использовать» просто смешно, что считается «употреблением»? Если это какое-то полностью принудительное использование, которое не служит никакой другой цели, я думаю, что вышеупомянутое делает свою работу.
ASDFGerte 01.08.2018 23:19
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
0
4
450
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Это лишь частичный намек, но он был слишком длинным для комментария. Одна из вещей, которую вы можете сделать с помощью 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) что & и ^ делают в этом случае

bigpotato 01.08.2018 23:31

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

ASDFGerte 01.08.2018 23:31

@Edmund, если вы хотите узнать больше о побитовых операциях в JavaScript, прочтите документацию по MDN. Также имейте в виду, что приведение чего-либо к строке происходит бесконечно медленнее, чем побитовая операция. developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…

SudoKid 01.08.2018 23:37

Если бы нужно было просто реализовать это без ограничений, используйте это: 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 он не работает быстрее. Но речь идет не об этом, а о тех странных дополнениях, которые «надо использовать».

ASDFGerte 01.08.2018 23:39

@Edmund ^ - это XOR, а & - побитовое AND. Проще всего перебирать маленькие числа и следить за битами. Например, начиная с 6 110& 5 101 дает вам 100. XOR, который с 6 дает вам 10 или 4 самый правый бит. Теперь вычтите 4 из 6, что приведет к удалению самого правого бита, и делайте это снова, пока у вас не закончатся биты.

Mark 01.08.2018 23:41

Этот n -= n ^ (n & (n -1)) можно было бы записать как n ^= n & -n, немного проще, но все же использует XOR.

harold 05.08.2018 12:06

@ASDFGerte Этот код из C, который строго типизирован. В JS вы можете получить значительный прирост скорости, сначала приведя n к int32 перед первой операцией, то есть n => { n = (n|0) - .... Я тестировал здесь несколько вариантов: jsperf.com/fast-int32-bit-count

Doin 09.11.2019 16:31

Другие вопросы по теме