Tricky Java solution with bitwise ops


  • 0
    F

    This can be done quickly with bitwise ops.
    The tricky part is that there is no unsigned int in Java.
    We should convert 'n' to a long before to play with bitwise ops in order to ignore sign extension.

    public class Solution {
        // you need treat n as an unsigned value
        public int reverseBits(int n) {
            long m = 0xFFFF_FFFFL & n;
            m = ((m & 0x5555_5555) << 1) | ((m & 0xAAAA_AAAA) >> 1);
            m = ((m & 0x3333_3333) << 2) | ((m & 0xCCCC_CCCC) >> 2);
            m = ((m & 0x0F0F_0F0F) << 4) | ((m & 0xF0F0_F0F0) >> 4);
            m = ((m & 0x00FF_00FF) << 8) | ((m & 0xFF00_FF00) >> 8);
            m = ((m & 0x0000_FFFF) << 16) | ((m & 0xFFFF_0000) >> 16);
            return (int) m;
        }
    }

  • 1
    R

    No need to convert n to long, actually only the last step when right move 16 bit, simply using unsigned bit shift.

    public int reverseBits(int x) {
        x = (x & 0x55555555) <<  1 | ((x >> 1) & 0x55555555);
        x = (x & 0x33333333) <<  2 | ((x >> 2) & 0x33333333);
        x = (x & 0x0F0F0F0F) <<  4 | ((x >> 4) & 0x0F0F0F0F);
        x = (x & 0x00FF00FF) <<  8 | ((x >> 8) & 0x00FF00FF);
        x = x << 16 | x >>> 16;
        return x;
    }
    

  • 0
    A
     public int reverseBits(int x) {
            x = (x & 0x55555555) <<  1 | ((x >> 1) & 0x55555555);
            x = (x & 0x33333333) <<  2 | ((x >> 2) & 0x33333333);
            x = (x & 0x0F0F0F0F) <<  4 | ((x >> 4) & 0x0F0F0F0F);
            x = (x & 0x00FF00FF) <<  8 | ((x >> 8) & 0x00FF00FF);
            return x << 16 | x >>> 16;
      }
    

    can be shorter.


  • 0

    can you explain this?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.