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 nombre 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

Créer un graphique à 256 lignes contenant un caractère char et son bit à inversion. étant donné un entier de 4 octets, prenez le premier caractère, regardez-le sur le graphique, comparez la réponse au dernier caractère de l'entier. si elles diffèrent ce n'est pas palindrome, si les mêmes sont répétées avec les caractères du milieu. s'ils diffèrent, ce n'est pas le palindrome.

Answer 3

J'ai toujours une fonction palindrome qui fonctionne avec les chaînes, qui renvoie vrai si c'est le cas, faux sinon, par ex. 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 4

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 la etc, qui aura O (N/2) où N est la taille de l'int. Si à un moment donné vos paires ne sont pas identiques, 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 5

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 6

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 7

Les éléments suivants doivent être adaptables à tout type non signé. (Les opérations sur bits sur les types signés ont tendance à être lourdes de 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 8

Parfois, il est bon de signaler un problème;

Il y a beaucoup de bonnes réponses ici sur la façon évidente de le faire, en analysant sous une forme ou une autre le modèle binaire. Je dois me demander, cependant, s'il y avait des solutions mathématiques? Y a-t-il des propriétés de nombres palendromiques dont nous pourrions tirer profit?

J'ai donc joué un peu avec les maths, mais la réponse aurait dû être évidente dès le départ. Il est trivial de prouver que tous les nombres palindromiques binaires doivent être soit impairs, soit nuls. C'est à peu près tout ce que j'ai pu obtenir avec. Un peu de recherche a montré une telle approche pour les palindromes décimaux, donc c'est soit un problème très difficile ou non solvable via un système formel. Il pourrait être intéressant de prouver le dernier ...

Answer 9

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 10

Espérons que 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 11

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 tous,

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

En Java, il est un moyen facile si vous comprenez airthmetic 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 14

#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; 
} 

Answer 15

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; 
}