Comment vérifier si la représentation binaire d'un entier est un palindrome?

Question

Comment vérifier si la représentation binaire d'un entier est un palindrome?

Answer 1

Puisque vous n'avez pas spécifié une langue pour le faire, voici un code C (et non la mise en œuvre la plus efficace, mais il devrait illustrer le point):

/* flip n */
unsigned int flip(unsigned int n)
{
    int i, newInt = 0;
    for (i=0; i<WORDSIZE; ++i)
    {
        newInt += (n & 0x0001);
        newInt <<= 1;
        n >>= 1;
    }
    return newInt;
}

bool isPalindrome(int n)
{
    int flipped = flip(n);
    /* shift to remove trailing zeroes */
    while (!(flipped & 0x0001))
        flipped >>= 1;
    return n == flipped;
}

EDIT fixe pour votre chose 10001.

Answer 2

Si tout va bien correcte:

_Bool is_palindrome(unsigned n)
{
    unsigned m = 0;

    for(unsigned tmp = n; tmp; tmp >>= 1)
        m = (m << 1) | (tmp & 1);

    return m == n;
}

Answer 3

Créer un graphique 256 lignes contenant char et il est peu inversé car. étant donné un nombre entier de 4 octets, prendre le premier caractère, regardez sur la carte, comparer la réponse à le dernier caractère de l'entier. si elles diffèrent, il ne palindrome, si le sont les mêmes répétition avec les caractères du milieu. si elles diffèrent, il est palindrome pas d'autre il est.

Answer 4

Beaucoup de solutions agréables ici. Permettez-moi d'ajouter un qui est pas le plus efficace, mais très lisible, à mon avis:

/* Reverses the digits of num assuming the given base. */
uint64_t
reverse_base(uint64_t num, uint8_t base)
{
  uint64_t rev = num % base;

  for (; num /= base; rev = rev * base + num % base);

  return rev;
}

/* Tells whether num is palindrome in the given base. */
bool
is_palindrome_base(uint64_t num, uint8_t base)
{
  /* A palindrome is equal to its reverse. */
  return num == reverse_base(num, base);
}

/* Tells whether num is a binary palindrome. */ 
bool
is_palindrome_bin(uint64_t num) 
{
  /* A binary palindrome is a palindrome in base 2. */
  return is_palindrome_base(num, 2);
}

Answer 5

Les points suivants doivent être adaptables à tout type non signé. (Opérations binaires sur les types signés ont tendance à se heurter à des problèmes.)

bool test_pal(unsigned n)
{
  unsigned t = 0;

  for(unsigned bit = 1; bit && bit <= n; bit <<= 1)
    t = (t << 1) | !!(n & bit);

  return t == n;
}

Answer 6

int palidrome (int num) 
{ 
  int rev = 0; 
  num = number; 
  while (num != 0)
  { 
    rev = (rev << 1) | (num & 1); num >> 1; 
  }

  if (rev = number) return 1; else return 0; 
}

Answer 7

Je l'ai toujours une fonction palindrome qui fonctionne avec des chaînes, qui retourne vrai si elle est, sinon false, par exemple en Java. La seule chose que je dois faire quelque chose comme:

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

Answer 8

Une version générique:

#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 9

Je pense que la meilleure approche est de commencer à la fin et travailler votre chemin vers l'intérieur, à savoir comparer le premier bit et le dernier bit, le second bit et le second au dernier bit, etc, qui aura O (N / 2 ) où N est la taille de l'int. Si à tout moment vos paires ne sont pas les mêmes, ce n'est pas un palindrome.

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 10

Parfois, il est bon de signaler un échec aussi;

Il y a beaucoup de grandes réponses ici sur la façon évidente de le faire, en analysant sous une forme ou une autre le motif de bits. Je me suis demandé, cependant, s'il y avait des solutions mathématiques? Y at-il des propriétés des nombres palendromic que nous pourrions tirer profit?

Je joue avec les maths un peu, mais la réponse aurait dû être évident dès le départ. Il est trivial de prouver que tous les nombres palindromes binaires doivent être soit impair ou zéro. C'est à peu près aussi loin que j'ai pu obtenir avec.

Un peu de recherche n'a pas montré cette approche pour palindromes décimales, il est donc soit un problème très difficile ou non résoluble par un système formel. Il pourrait être intéressant de prouver ce dernier ...

Answer 11

    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 12

bool PaLInt (unsigned int i, unsigned int bits)
{
    unsigned int t = i;
    unsigned int x = 0;
    while(i)
    {
        x = x << bits;        
        x = x | (i & ((1<<bits) - 1));
        i = i >> bits;
    }
    return x == t;
}

1. Appel PalInt (i, 1) pour pallindromes binaires
2. Appel PalInt (i, 3) pour Octal Palindromes
3. Appel PalInt (i, 4) pour Hex Palindromes

Answer 13

Je sais que cette question a été posté il y a 2 ans, mais j'ai une meilleure solution qui ne dépend pas de la taille de texte et tout,

int temp = 0;
int i = num;
while (1)
{ // let's say num is the number which has to be checked
    if (i & 0x1)
    {
        temp = temp + 1;
    }
    i = i >> 1;
    if (i) {
        temp = temp << 1;
    }   
    else   
    {
        break;
    }
}   

return temp == num;

Answer 14

En Java, il est un moyen facile si vous comprenez l'arithmétique binaire de base, est le code ici:

    public static void main(String []args){
        Integer num=73;
        String bin=getBinary(num);
        String revBin=reverse(bin);
        Integer revNum=getInteger(revBin);

        System.out.println("Is Palindrome: "+((num^revNum)==0));

     }

     static String getBinary(int c){
         return Integer.toBinaryString(c);
     }

     static Integer getInteger(String c){
         return Integer.parseInt(c,2);
     }

     static String reverse(String c){
         return new StringBuilder(c).reverse().toString();
     }

Answer 15

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    unsigned int n = 134217729;
    unsigned int bits = floor(log(n)/log(2)+1);
    cout<< "Number of bits:" << bits << endl;
    unsigned int i=0;
    bool isPal = true;
    while(i<(bits/2))
    {
        if(((n & (unsigned int)pow(2,bits-i-1)) && (n & (unsigned int)pow(2,i))) 
                                         ||    
        (!(n & (unsigned int)pow(2,bits-i-1)) && !(n & (unsigned int)pow(2,i))))
        {
            i++;
            continue;
        }
        else
        {
            cout<<"Not a palindrome" << endl;
            isPal = false;
            break;
        }
}

    if(isPal)
        cout<<"Number is binary palindrome" << endl;
}