Zmienne każda para bitów w bajcie

To było pytanie zadane przez przedstawiciela firmy NVIDIA na targach kariery:Zmienne każda para bitów w bajcie

Napisz małego, wydajnego kodu zamienią każdą parę bitów wewnątrz bajt; na przykład 10 11 01 10 powinien stać się 01 11 10 01.

Czy istnieje bardziej „efektywne” sposób to zrobić, niż wykonując for pętli przez każdego innego indeksu? Mój kod był mały, ale nie mogę sobie wyobrazić, jak dużo bardziej "wydajne" może to osiągnąć niż pętla ... Zgaduję, że istnieje sposób na użycie XOR, aby uniknąć pętli, ale nie mogę rozwiązać.

Dzięki!

Źródło

2011-01-25 Mehrdad

To 'wasn't' pytanie? Nie widzę tego ... –

@MrDisappointment Podejrzewam, że gdyby to było pytanie, Mehrdad naruszyłby pisemną umowę lub zażądałby nie dzielenia się tym pytaniem z innymi. – Phrogz

@MrDisappointment: LOL przepraszam, literówka; naprawiono XD ... @Phrogs: Nie było takiej zgody ani nic, to było otwarte targi kariery z setką lub dwiema osobami; żadnych podpisów ani niczego w tym rodzaju. :) – Mehrdad

Można użyć tabeli odnośników 256 wjazdu.

Alternatywnie ((x & 0x55) << 1) | ((x & 0xAA) >> 1).

Źródło

2011-01-25 00:32:42

+1. Jeśli zależy Ci na szybkości, tabela odpowiedzi jest odpowiedzią. Używa 256 bajtów dla tabeli odnośników, ale, jak w przypadku większości optymalizacji, jest to kompromis między czasoprzestrzenią. Jeśli nie chcesz marnować tej przestrzeni, prawdopodobnie nie uzyskasz więcej niż kilka zmian i operacji bitowych. – paxdiablo

Oczywiście uważaj na typ 'signed'. –

+1 Myślę, że to drugie rozwiązanie, ponieważ jest to najbardziej zwięzłe i bardzo wydajne ... argh, tak łatwe, a jednocześnie tak trudne. :( – Mehrdad

tabeli przeglądowej (chyba że istnieje jakiś szczególny NVIDA specyficzne rozwiązanie szukał).

Źródło

2011-01-25 00:32:06

Nie szukał rozwiązania specyficznego dla NVIDII, ale szukał szybkiego * i * małego kodu ... czy rozwiązanie do wyszukiwania tabeli się liczy? (choć wprawdzie nie pomyślałem o tym ...) – Mehrdad

@Mehrdad: Wyszukiwanie tabeli jest po prostu "pierwszą rzeczą, która przychodzi na myśl" z tego typu problemami. Z pewnością może być lepszy, sprytny hack. Można również rozważyć mniejszą 16-bajtową (lub nawet 8-bajtową) tabelę połączoną z niektórymi operacjami zmiany/maski, aby wyszukać 4 bity na raz. Nie jestem pewien, gdzie może być ta słodka. –

Coś jak to powinno działać

(i >> 1) & 01010101 + (i << 1) & 10101010

i >> 1 przesuwa wszystko o 1 bit w prawo, a & 01010101 pozostawia tylko bity na pozycjach parzystych.
Druga część dotyczy pozycji bitowych nieparzystych w tej samej grupie.

Nie jestem pewien, jak jest to skuteczne.

Źródło

2011-01-25 00:32:59

+1 To jest cholernie sprytne, dziękuję ... Myślałem o jakimś sposobie użycia przesunięć bitowych, ale nie mogłem tego rozgryźć. Cool !! :) – Mehrdad

Tak, wolę | operatora do operatora +, ale tego samego rozwiązania. I oczywiście twój kod jest pseudo dla reprezentacji base-2. – CashCow

Ponieważ w bajcie istnieje tylko 256 możliwych kombinacji, wydaje się, że jest to dobry kandydat do korzystania z rozwiązania opartego na tabeli odnośników w dowolnym momencie, w którym stała prędkość wykonywania jest ważniejsza niż wstępne obliczenie i/lub całkowite wykorzystanie pamięci.

Na przykład:

lookupTable[00000000] = 00000000 
lookupTable[00000001] = 00000010 
lookupTable[00000010] = 00000001 
...

Źródło

2011-01-25 00:34:12 Coxy

Zdecydowanie nie mały kod. :( – Mehrdad

Zdecydowanie nie zgadzam się, ale pamiętaj, że mały kod nie zawsze jest skuteczny, a efektywny kod nie zawsze jest mały – Coxy

Brak pamięci podręcznej jest problemem z tabelami odnośników Ogólnie rzecz biorąc, to małe, łatwiej jest po prostu obliczyć wynik Myślę, że ... –

Bez tabeli przeglądowej (lub do generowania rzeczy w pierwszej kolejności) można również:

przesunięcie w lewo i I z lewa-bitowej masce (10101010)
przesunięcie w prawo i ORAZ z maską z prawą bitą (01010101)
OR razem wyniki.

przesunięty w lewo jest 01 10 11 00 maskowane 10101010 daje nam 00 10 10 00

przesunięta w prawo (oryginalna) jest maskowane 01010101 daje nam 01 01 00 01

LUB nasze wyniki wraz

Więc w C lub C++ można zrobić

unsigned char bitswap(unsigned char uch) 
{ 
    return ((uch<<1) & 0xAA) | (uch>>1) & 0x55); 
}

Wystarczy uruchomić, że dla wszystkich wartości od 0x00 do 0xFF (zapewnić pętla kończy!), Aby wygenerować „stół”.

Źródło

2011-01-25 15:20:20 CashCow

Dziękuję za wyjaśnienie! – Chayemor

Dla 32-bitowej interger w java ..

public int swapOddEvenbits(int x) 
{ 
    return ( ((x & 0xaaaaaaaa) >> 1 | ((x & 0X55555555) << 1)); 

}

Jeśli pracujesz z 64-bitowymi, trzeba byłoby zmienić maskę ..

Źródło

2014-07-19 17:52:26

Odpowiedz

Powiązane problemy