Обратные биты JavaScript

Question

Проблема стандартная, но решение в JavaScript требует гораздо больше усилий для кодирования.

Я получил решение, но мой ответ приходит наполовину от желаемого.

Описание проблемы

Инвертировать биты 32-разрядного целого числа без знака A.

Ограничения задачи

0 <= A < = 2 ^ 32 </p>

Формат ввода

Первый и единственный аргумент ввода содержит целое число A.

Формат вывода

Возвращает единственное целое число без знака, обозначающее минимальное значение xor.

Пример ввода

Input 1:
0
Input 2:
3

Пример вывода

Output 1:
0
Output 2:
3221225472

Мое решение

function modulo(a, b) {
        return a - Math.floor(a/b)*b;
}
function ToUint32(x) {
    return modulo(parseInt(x), Math.pow(2, 32));
}
function revereBits(A){
    A = A.toString(2);
    while (A.length < 31){
        A = "0"+A;
    }
    var reverse = 0;
    var NO_OF_BITS = A.length;
    for(var i = NO_OF_BITS; i >= 1; i--){
        var temp = (parseInt(A, 2) & (1 << i - 1));
        if(temp){
            reverse |= 1 << (NO_OF_BITS - i);

        }
    } 
    if( reverse << 1 < 0 ) reverse = ToUint32(reverse << 1);
    return reverse;

}

Теперь в строке

 if( reverse << 1 < 0 ) reverse = ToUint32(reverse << 1);

Вы видите, что я должен удвоить ответ. Однако я не могу понять, почему это необходимо.

Я выбрал подход из https://www.geeksforgeeks.org/write-an-efficient-c-program-to-reverse-bits-of-a-number/

Пришлось сделать несколько корректировки к нему. Например, запустите l oop от 31 до 1, а не от 0 до 31. Последний дает отрицательные значения в первой операции сдвига влево для самого i = 0.

Может кто-нибудь помочь исправить это решение и указать на проблему в этом?

ОБНОВЛЕНИЕ - Проблема связана с манипулированием битами. Так что, ребята, пожалуйста, не отвечайте и не комментируйте что-либо, состоящее из встроенных строковых функций Javascript. Ура!

Answer 1

Попробуйте это:

function reverseBits(num) {

    let reversed = num.toString(2);
    const padding = "0";
    reversed = padding.repeat(32 - reversed.length) + reversed;
    return parseInt(reversed.split('').reverse().join(''), 2);
}

console.log(reverseBits(0)); // 0
console.log(reverseBits(3)); // 3221225472

Answer 2

Вы должны быть в состоянии сделать это, используя только побитовые операторы и типизированный массив для решения проблемы со знаком:

function rev(x) {
  x = new Uint32Array([x]);
  x[0] = (x[0] & 0x55555555)  <<   1 | (x[0] & 0xAAAAAAAA) >>  1;
  x[0] = (x[0] & 0x33333333)  <<   2 | (x[0] & 0xCCCCCCCC) >>  2;
  x[0] = (x[0] & 0x0F0F0F0F)  <<   4 | (x[0] & 0xF0F0F0F0) >>  4;
  x[0] = (x[0] & 0x00FF00FF)  <<   8 | (x[0] & 0xFF00FF00) >>  8;
  x[0] = (x[0] & 0x0000FFFF)  <<  16 | (x[0] & 0xFFFF0000) >> 16;

  return x[0];
}

console.log(rev(0).toString(2)) // "0"
console.log(rev(3).toString(2)) // "11000000000000000000000000000000"

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

Обновление : Как указал @harold в комментарии, сдвиг вправо с нулевой заливкой возвращает unsigned (это единственный побитовый оператор для этого), поэтому мы можем опустить типизированный массив и просто добавить >>> 0 перед return:

function rev(x) {
  x = (x & 0x55555555)  <<   1 | (x & 0xAAAAAAAA) >>  1;
  x = (x & 0x33333333)  <<   2 | (x & 0xCCCCCCCC) >>  2;
  x = (x & 0x0F0F0F0F)  <<   4 | (x & 0xF0F0F0F0) >>  4;
  x = (x & 0x00FF00FF)  <<   8 | (x & 0xFF00FF00) >>  8;
  x = (x & 0x0000FFFF)  <<  16 | (x & 0xFFFF0000) >> 16;

  return x >>> 0;
}

console.log(rev(0).toString(2)) // "0"
console.log(rev(3).toString(2)) // "11000000000000000000000000000000"

На самом деле, выполнение >>> 0 обычно используется для имитировать ToUint32 в JS polyfilll; Например:

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/every

    // 2. Let lenValue be the result of calling the Get internal method
    //    of O with the argument "length".
    // 3. Let len be ToUint32(lenValue).
    var len = O.length >>> 0;