Reverse Bits JavaScript

Question

The problem is standard but the solution in JavaScript takes a lot more effort to code.

I got the solution but my answer is coming half of what is desired.

Problem Description

Reverse the bits of a 32-bit unsigned integer A.

Problem Constraints

0 <= A <= 2^32

Input Format

The first and only argument of input contains an integer A.

Output Format

Return a single unsigned integer denoting minimum xor value.

Example Input

Input 1:
0
Input 2:
3

Example Output

Output 1:
0
Output 2:
3221225472

My solution


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;

}

Now, in the line

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

You see that I have to double the answer. I cannot, however, get the part of why is this required.

I took the approach from https://www.geeksforgeeks.org/write-an-efficient-c-program-to-reverse-bits-of-a-number/

Had to make few adjustments to it. For example, run the loop from 31 to 1 rather than 0 to 31. The latter gives negative values in first left shift operation for i = 0 itself.

Can someone please help in fixing this solution and point to the problem in this?

UPDATE - Problem is related to Bit manipulation. So guys, please don't answer or comment for anything consisting of in-built string functions of Javascript. Cheers!

Once you've built A as a string, you could split the string into an array, call .reverse() on that, join it back together, and then pass it to parseInt(A, 2). — Pointy
– Pointy, Commented Feb 14, 2020 at 13:02
This: parseInt(a.toString(2).padStart(32, 0).split('').reverse().join(''), 2) — user5734311
– user5734311, Commented Feb 14, 2020 at 13:06
I'd say the problem is related to not having unsigned integers in javascript. — orithena
– orithena, Commented Feb 14, 2020 at 13:33
Yes @orithena That is an issue. That's the very reason ToUint32 is there as an extra function. But my concern is the last part where I have to do one extra left shift. (reverse << 1). It's bugging me — HalfWebDev
– HalfWebDev, Commented Feb 14, 2020 at 13:36

ZER0 · Accepted Answer · 2022-07-22 05:19:42Z

7

You should be able to do it using just bitwise operators, and a typed array to solve the sign issue:

Update Changing slightly approach of the rev function after @bryc comment. Since having multiple function for "history" purpose makes the answer difficult to read, I'm putting first the latest code. However, I'm keeping the comments about the different steps – the rest can be found in the edit history.

function rev(x) {
    x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
    x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
    x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
    x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
    x = (x >>> 16) | (x << 16);

    return x >>> 0;
}

This is the same code you would write in other languages as well to reverse bits, the only difference here is the addition of the typed array.

As @harold pointed out in the comment, the zero-fill right shift returns an unsigned (it's the only bitwise operator to do so) therefore we can omit the typed array and just add >>> 0 before the return.

In fact, doing >>> 0 is commonly used to simulate the ToUint32 in JS polyfilll; e.g.:

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;

edited Jul 22, 2022 at 5:19

answered Feb 14, 2020 at 13:30

ZER0

25.5k5 gold badges53 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

HalfWebDev Over a year ago

Yes Sir, But this is complicated and won't strike to mind. Can you help fix a bug in my code? I believe, I'm on right track

ZER0 Over a year ago

I thought the question was how to reverse bit in JavaScript: this is how you reverse bits in JavaScript, just using bitwise operators. There is nothing complicated in that, is the same code you can find in C as well and any languages that can deal with bits. If you want to reverse bits in your own way is cool, but it's not efficient neither is how you do it in JS (or any other languages). Bottom line: you might want to edit the title of your question, it doesn't reflect what you want to obtain.

user555045 Over a year ago

Well I meant (x & 0xFFFF0000) >> 16 etc, shouldn't those shifts be the >>> variant, to avoid the sign bit spreading all over the place?

user555045 Over a year ago

@ZER0 I know it reverts to signed, doesn't matter. The shifts however must be unsigned, otherwise they copy the sign bit all over the place. You can put in rev(0x80000000) or something similar to see it go wrong, using >>> fixes that.

ZER0 Over a year ago

@bryc my bad, I had a typo: the last right shift should also be a zero-fill right shift (answer updated)

|

lejlun · Accepted Answer · 2021-08-23 09:44:34Z

4

function reverseBits(integer, bitLength) {
  if (bitLength > 32) {
    throw Error(
      "Bit manipulation is limited to <= 32 bit numbers in JavaScript."
    );
  }

  let result = 0;
  for (let i = 0; i < bitLength; i++) {
    result |= ((integer >> i) & 1) << (bitLength - 1 - i);
  }

  return result >>> 0; // >>> 0 makes it unsigned even if bit 32 (the sign bit) was set
}

edited Aug 23, 2021 at 9:44

lejlun

4,4312 gold badges18 silver badges31 bronze badges

answered Apr 12, 2021 at 19:41

Joakim L. Christiansen

1,43911 silver badges16 bronze badges

1 Comment

Joakim L. Christiansen Over a year ago

What's up with the "semicolon-police" adding semicolons to my code? It's not C++...

Jelle Bruisten · Accepted Answer · 2020-02-14 13:14:06Z

1

Try this:

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

answered Feb 14, 2020 at 13:14

Jelle Bruisten

4416 silver badges11 bronze badges

5 Comments

HalfWebDev Over a year ago

Not looking for in-built function solutions

HalfWebDev Over a year ago

I didn't change anything. My solution approach says everything

Heretic Monkey Over a year ago

@kushalvm Nothing in the question says anything about not using "in-built functions" before the edit.

HalfWebDev Over a year ago

The way problem is described and the reference link for geeksforgeeks should say a volume that this is a problem-solving question rather than achieving any workable solution. The official term is competitive programming. Try it sometime!

Heretic Monkey Over a year ago

@kushalvm Read How to Ask. All information relevant to the question must be in the question itself. Please don't condescend to others who are trying to help make this the best site for great questions and answers.

Collectives™ on Stack Overflow

Reverse Bits JavaScript

3 Answers 3

12 Comments

1 Comment

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

12 Comments

1 Comment

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related