กลับลำดับบิตจริงของตัวเลขที่กำหนดใน Java

ภาพรวมปัญหา

ได้รับจำนวนเต็ม n ≥ 0 ต้องกลับลำดับบิตของ n (ในรูปแบบทวีคูณจริง ไม่รวม leading zeros) และคืนค่าทศนิยมของผลลัพธ์

ตัวอย่าง

Input: 13

Output: 11

(13)₁₀ = (1101)₂ → กลับบิต → (1011)₂ = (11)₁₀

Input: 18

Output: 9

(18)₁₀ = (10010)₂ → กลับบิต → (1001)₂ = (9)₁₀

แนวทางการแก้ปัญหา

• ใช้ตัวแปร rev_input เก็บผลลัพธ์
• วนลูป while (input > 0):
  • rev_input <<= 1 (เลื่อนซ้าย ทำที่ว่างสำหรับบิตใหม่)
  • ถ้า (input & 1) == 1 ให้ rev_input ^= 1 (เซตบิต LSB เป็น 1)
  • input >>= 1 (เลื่อนขวา เพื่อนำบิตถัดไปมา)
• คืนค่า rev_input

ตัวอย่างโค้ด Java

class TutorialsPoint {
    public static int reverseBinaryBits(int input) {
        int rev_input = 0;
        while (input > 0) {
            rev_input <<= 1;
            if ((input & 1) == 1) rev_input ^= 1;
            input >>= 1;
        }
        return rev_input;
    }

    public static void main(String[] args) {
        int input = 13;
        System.out.println("Reverse actual bits of the given number");
        System.out.println(reverseBinaryBits(input));
    }
}

ผลลัพธ์

Reverse actual bits of the given number 11