Bitowy palindrom

pytanie zadane 26 lutego 2018 w C i C++ przez Nitj'Sefni Nowicjusz (150 p.)

Cześć.
Mam za zadanie uzupełnić kod tak, aby sprawdzał czy dana liczba (unsigned short int) jest bitowym palindromem, np.: 384(dec) - 0000000110000000(bin).

#include <iostream>
using namespace std;
int main(void) 
{
unsigned short int val;
bool ispalindrome = false;
cout << "value = ";
cin >> val;
// Insert your code here
if(ispalindrome)
cout << val << " is a bitwise palindrome" << endl;
else
cout << val << " is not a bitwise palindrome" << endl;
return 0;
}

Proszę o pomoc, ponieważ jakoś nie mogę wymyślić, jak to zrobić.
Z góry dziękuję.

4 odpowiedzi

odpowiedź 26 lutego 2018 przez mokrowski Mędrzec (158,940 p.)
wybrane 27 lutego 2018 przez Nitj'Sefni

Najlepsza

#include <iostream>
#include <bitset>
#include <iomanip>

bool isBitPalindrome(unsigned short int data) {
    unsigned short int val = data;
    val = ((val & 0x5555) << 1) | ((val & 0xAAAA) >> 1);
    val = ((val & 0x3333) << 2) | ((val & 0xCCCC) >> 2);
    val = ((val & 0x0F0F) << 4) | ((val & 0xF0F0) >> 4);
    val = ((val & 0x00FF) << 8) | ((val & 0xFF00) >> 8);
    return val == data;
}

void show(unsigned short int data) {
    std::cout << std::hex << "0x" << std::setw(4)
        << std::setfill('0') << data
        << ' ' << std::bitset<16>(data)
        << " isBitPalindrome? " << std::boolalpha
        << isBitPalindrome(data) << '\n';
}

int main() {
    unsigned short int val = 0x8001;
    show(val);
    val = 0x0001;
    show(val);
}

komentarz 27 lutego 2018 przez Treners Początkujący (310 p.)

Możesz wytłumaczyć ten kod?

komentarz 27 lutego 2018 przez mokrowski Mędrzec (158,940 p.)

Linie 7-10 wykonują lustrzane odwrócenie bitowe danych.

W 11'tej sprawdzam czy te lustrzane odbicie równe jest pierwotnej liczbie.

Strona z operacjami bitowymi: https://graphics.stanford.edu/~seander/bithacks.html

Książka z obszernym omówieniem zależności pomiędzy operacjami bitowymi i arytmetycznymi: https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685

Wersja polska tej książki (nie wiem jaka jest jakość, nie czytałem tej wersji): https://helion.pl/ksiazki/uczta-programistow-henry-s-warren,sztuha.htm#format/d

komentarz 27 lutego 2018 przez Paweł Dymek Bywalec (2,300 p.)

@mokrowski,

Twoja wiedza oraz umiejętność czytania zapisu 16 w locie robi wrażenie, ale


王明：这　是　什么？
李红：这　是　书。
王明：那　是　什么？
李红：那　是　钢笔。
王明：那　是　杂志　吗？
李红：不，那　不是　杂志。那　是　字典。

Dla początkującego jest to równie czytelne, ale mój kod się nie skompiluje.

To co napisałeś można prościej (uwzględniając tyle bitów ile zakłada typ zmiennej:

bool Sprawdz(unsigned short int liczba)
{
    for (unsigned short int a=0;a<(sizeof(liczba)*8-1);a++)
    {
        if(bool(liczba&(1<<a)) != bool(liczba&(1<<(sizeof(liczba)*8-1-a))))
            return false;//dwa lustrzane bity się różnią, zwracamy FALSE
    }
    return true;
}

Przyznasz chyba, że powyższy kod jest dużo czytelniejszy i łatwiejszy do zrozumienia, ponadto jak zajdzie potrzeba zmiany typu z short na zwykły int to nie będzie trzeba zmieniać funkcji. 2 jajka na śniadanie łatwiej ugotować w garnuszku niż w kotle:P

komentarz 27 lutego 2018 przez mokrowski Mędrzec (158,940 p.)

@Paweł Dymek

Nie. Nie przyznam że jest czytelniejszy. Nie przyznam także że jest szybszy. Porównaj wyniki: https://godbolt.org/g/iHS8Wh

Dziękuję za uznanie co do umiejętności czytania hex. Polecam. To niezbędna umiejętność.

PS. Ja wolę być Li Hong...

komentarz 27 lutego 2018 przez Paweł Dymek Bywalec (2,300 p.)

@mokrowski

Twierdzisz, że mój kod 3 razy krótszy, prosty, nie jest bardziej czytelny niż Twój kod w którym przeważa zapis szesnastkowy (praktycznie nieczytelny dla początkujących). Dla Ciebie pewnie nie robi to różnicy, ale tak jak pisałem, dla początkujących jest ona wyraźna.

Jak wielu zmian potrzeba w Twojej funkcji, aby zmnienić typ argumentu na 8bitowy, następnie na 32, a na koniec na 64? U mnie tylko zmienić go w argumencie.

Piszesz o prędkości wykonania się kodu, który np. u mnie trwa pomiędzy 6 a 14 ms czyli jest tak mały, że prawie niemierzalny. Twój daje te same wyniki.

Uproszczenie kodu i uczynienie go maksymalnie łatwym do zmian jest moim zdaniem rozsądniejsze w tym przypadku niż rozciąganie go na 3 razy dłuższy, (dla 64 bitowego inta nawet więcej niż 3) tylko po to, aby był "szybszy". Gra niewarta świeczki. Chętnie poznam rozsądne argumenty za wydłużaniem i komplikowaniem kodu W TYM PRZYKLADZIE.

Zgodzę się, że przy ogromnych projektach optymalizuje się co tylko możliwe.

odpowiedź 26 lutego 2018 przez Paweł Dymek Bywalec (2,300 p.)

1. Sprawdź ile bitów potrzeba do zapisu liczby, np. tak:

int ileBitow(int liczba)
{
    int a=1;
    while(pow(2,a)<=liczba)
        a++;
        return a;
}

2. Sprawdzaj kolejno bit z końca i początku przechowując ich numery z zmiennych, zmienne odpowiednio inkrementuj(numer poczatkowego bitu) i dekrementuj (numer koncowego) i porównuj je tak długo jak numer koncowego bita jest wiekszy od poczatkowego, np.

bool Sprawdz(int liczba)
{
    int ileBitow=IleBitow(liczba);
    int p=0,k=ileBitow-1;// pierwszy bit ma numer 0 ostatni to ilosc bitow -1
    while(p<k)
    {
        if(bool(liczba&(1<<p)) != bool(liczba&(1<<k)))
            return false;//dwa lustrzane bity się różnią, zwracamy FALSE
        p++;
        k--;
    }
    return true;//p (poczatek) jest wiekszy od k (konca) czyli porownalismy juz wszsytkie bity i skoro doszlo do tego momentu to nie różniły się w lustrzanym odbiciu
}

Musisz to zaopatrzec w sprawdzenie czy zmienna nie jest ujemna, wtedy sytuacja sie zmienia, bo o ile w 8 bitach zapiszesz dowolną liczbę od 0 do 255 (uint8_t czyli 8bitowy typ liczby naturalnej) o tylko ujemną już tylko od -128 czyli zmienia nam to pojemność o połowę -1 (dla int8_t). Dla typu int8_t potrzebujesz do zapisu 127 8 bitów ale do 128 już 9 bitów, natomiast -128 możesz zapisać w 8. Mam nadzieję, że w miarę wyjaśniłem :)