Problem

Given a positive integer, determine if its binary (bit) representation is a palindrome. For example, 5 is a palindrome because 5 = 101. Also, 9 is a palindrome because 9 = 1001.

Examples

Example 1:

Input: 5 Output: true Explanation: 5 in binary is 101, which is a palindrome.

Example 2:

Input: 4 Output: false Explanation: 4 in binary is 100, which is not a palindrome.

Example 3:

Input: 9 Output: true Explanation: 9 in binary is 1001, which is a palindrome.

Constraints:

  • 0 <= n <= 2^31 - 1

Solution

Method 1 – Reverse Bits and Compare

Intuition: Reverse the bits of the number and compare with the original. If they are equal, the bit representation is a palindrome.

Approach:

  1. Copy the input number.
  2. Reverse its bits by shifting and OR-ing the lowest bit.
  3. Compare the reversed number to the original.

Code

1
2
3
4
5
6
7
8
9

def is_palindrome_bits(n):
    if n < 0:
        return False
    rev = 0
    num = n
    while num > 0:
        rev = (rev << 1) | (num & 1)
        num >>= 1
    return rev == n
1
2
3
4
5
6
7
8
9

bool isPalindromeBits(int n) {
    if (n < 0) return false;
    int rev = 0, num = n;
    while (num > 0) {
        rev = (rev << 1) | (num & 1);
        num >>= 1;
    }
    return rev == n;
}
1
2
3
4
5
6
7
8
9

public boolean isPalindromeBits(int n) {
    if (n < 0) return false;
    int rev = 0, num = n;
    while (num > 0) {
        rev = (rev << 1) | (num & 1);
        num >>= 1;
    }
    return rev == n;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func isPalindromeBits(n int) bool {
    if n < 0 {
        return false
    }
    rev, num := 0, n
    for num > 0 {
        rev = (rev << 1) | (num & 1)
        num >>= 1
    }
    return rev == n
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

fun isPalindromeBits(n: Int): Boolean {
    if (n < 0) return false
    var rev = 0
    var num = n
    while (num > 0) {
        rev = (rev shl 1) or (num and 1)
        num = num shr 1
    }
    return rev == n
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

pub fn is_palindrome_bits(n: i32) -> bool {
    if n < 0 { return false; }
    let mut rev = 0;
    let mut num = n;
    while num > 0 {
        rev = (rev << 1) | (num & 1);
        num >>= 1;
    }
    rev == n
}

Complexity

  • Time: O(k) where k is the number of bits in n
  • Space: O(1)

Method 2 – Two Pointer Bitwise Check

Intuition: Compare the i-th bit from the left and right, moving towards the center.

Approach:

  1. Find the highest set bit (leftmost 1).
  2. Use two pointers: left (most significant bit), right (least significant bit).
  3. Compare bits at left and right; if any mismatch, return False.
  4. Move pointers inward until they meet.
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def is_palindrome_bits_twoptr(n):
    if n < 0:
        return False
    left = n.bit_length() - 1
    right = 0
    while left > right:
        if ((n >> left) & 1) != ((n >> right) & 1):
            return False
        left -= 1
        right += 1
    return True

Complexity

  • Time: O(k)
  • Space: O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

integer nResultNum = 0
integer nInputNumCopy = nInputNum

while nInputNumCopy > 0
 nResultNum = nResult << 1;
 if nInputNumCopy & 1 == 1
 nResultNum = nResultNum | 1;
 nResultNumCopy = nResultNumCopy >> 1;
end while

if nResultNumCopy == nInputNum
 return true

return false

Here is the implementation of the pseudocode :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public static boolean isPalindrome(int input){
 if ( input < 0)
 return false;

 int inputCopy = input;
 int resultantNumber = 0;
//reverse the bits in the number
 while (inputCopy > 0){
 resultantNumber <<= 1;
 if ((inputCopy & 1)!=0) {
 resultantNumber |=1;
 }
 inputCopy >>= 1;
 }

 if (input == resultantNumber)
 return true;

 return false;

}

In the program, we first check for invalid inputs. resultantNumber  is the number whose bit representation is the reverse of the input number. inputCopy  is the copy of the input number. Since we’ll destroy the value in the process, we must make copy of it so that we can compare the result to the original input later on. We first reverse the number and then compare them to be equal.