Как проверить, является ли двоичное представление целого числа палиндромом?

Question

Как проверить, является ли двоичное представление целого числа палиндромом?

Answer 1

    public static bool IsPalindrome(int n) {
        for (int i = 0;  i < 16; i++) {
            if (((n >> i) & 1) != ((n >> (31 - i)) & 1)) {
                return false;
            }
        }
        return true;
    }

Answer 2

Иногда также полезно сообщить об ошибке;

Есть много отличных ответов об очевидном способе сделать это, анализируя в той или иной форме битовый паттерн. Я задался вопросом, хотя, были ли какие-нибудь математические решения? Существуют ли свойства чисел, которые мы могли бы использовать?

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

Небольшое исследование не показало такого подхода к десятичным палиндромам, так что это либо очень сложная проблема, либо ее нельзя решить с помощью формальной системы. Может быть интересно доказать последнее ...

Answer 3

Общая версия:

#include <iostream>
#include <limits>
using namespace std;

template <class T>
bool ispalindrome(T x) {
    size_t f = 0, l = (CHAR_BIT * sizeof x) - 1;
    // strip leading zeros
    while (!(x & (1 << l))) l--;
    for (; f != l; ++f, --l) {
        bool left = (x & (1 << f)) > 0; 
        bool right = (x & (1 << l)) > 0;
        //cout <<  left << '\n';
        //cout <<  right << '\n';
        if (left != right) break;
    }
    return f != l;
}       

int main() {
    cout << ispalindrome(17) << "\n";
}

Answer 4

Я думаю, что лучший подход - это начать с конца и двигаться внутрь, т. Е. Сравнить первый бит и последний бит, второй бит и второй-последний бит и т. Д., Которые будут иметь O (N / 2). ) где N - размер целого Если в какой-то момент ваши пары не совпадают, это не палиндром.

bool IsPalindrome(int n) {
    bool palindrome = true;
    size_t len = sizeof(n) * 8;
    for (int i = 0; i < len / 2; i++) {
        bool left_bit = !!(n & (1 << len - i - 1));
        bool right_bit = !!(n & (1 << i));
        if (left_bit != right_bit) {
            palindrome = false; 
            break;
        }
    }
    return palindrome;
}

Answer 5

У меня всегда есть функция палиндрома, которая работает со строками, которая возвращает true, если это так, иначе false, например, на Яве. Единственное, что мне нужно сделать, это что-то вроде:

int number = 245;
String test = Integer.toString(number, 2);
if(isPalindrome(test)){
   ...
}