Wdrażanie logiczna negacja tylko operatorów bitowe (z wyjątkiem!)

Question

~ &^| + << >> są tylko operacje mogę używać

Przed I nadal jest to pytanie zadania domowe, byłem zatrzymany w tej sprawie przez naprawdę długi czas.

Moje oryginalne podejście: Myślałem, że! X można zrobić z dopełnieniem dwóch i zrobić coś z jego dodatkiem odwrotnym. Wiem, że Xor prawdopodobnie tu jest, ale nie mam pojęcia, jak do tego podejść.

Dla zapisu: Nie mogę również używać warunkowych, pętli, ==, itp., Tylko funkcje (bitowe), o których wspomniałem powyżej.

Na przykład:

!0 = 1 
!1 = 0 
!anything besides 0 = 0 

Answer 1

Zakładając np 8-bitowy niepodpisany typ:

~(((x >> 0) & 1) 
| ((x >> 1) & 1) 
| ((x >> 2) & 1) 
... 
| ((x >> 7) & 1)) & 1 

Answer 2

Poniższy kod kopiuje dowolny 1 bit do wszystkich pozycji. To mapuje wszystkie non-zera na 0xFFFFFFFF == -1, pozostawiając 0 pod 0. Następnie dodaje 1, mapowanie -1 do 0 i do .

x = x | x << 1 | x >> 1 
x = x | x << 2 | x >> 2 
x = x | x << 4 | x >> 4 
x = x | x << 8 | x >> 8 
x = x | x << 16 | x >> 16 

x = x + 1 

Answer 3

Można po prostu zrobić ~ x & 1, ponieważ to daje 1 0 i 0 dla wszystkiego innego

Answer 4

Zakładając 32 bit unsigned int:

(((x>>1) | (x&1)) + ~0U) >> 31 

powinno wystarczyć

Answer 5

Dla 32-bitowej liczby całkowitej ze znakiem x

// Set the bottom bit if any bit set. 
x |= x >> 1; 
x |= x >> 2; 
x |= x >> 4; 
x |= x >> 8; 
x |= x >> 16; 

x ^= 1; // Toggle the bottom bit - now 0 if any bit set. 
x &= 1; // Clear the unwanted bits to leave 0 or 1. 

Answer 6

Zakładając, że x jest podpisany, należy zwrócić 0 dla dowolnej liczby, a nie 0 i 1 dla zera.

Prawe przesunięcie na podpisanej liczbie całkowitej zwykle jest przesunięciem arytmetycznym w większości implementacji (np. Bit znaku jest kopiowany). Dlatego przesunięcie w prawo x przez 31 i jego negację przez 31. Jeden z tych dwóch będzie liczbą ujemną, a więc prawy przesunięty o 31 będzie równy 0xFFFFFFFF (oczywiście jeśli x = 0 to prawy przesuw da 0x0, co jest potrzebne) . Nie wiesz, czy x lub jego negacja jest liczbą ujemną, więc po prostu "albo" je razem, a dostaniesz to, czego chcesz. Następnie dodaj 1 i swoje dobro.

realizacja:

int bang(int x) { 
    return ((x >> 31) | ((~x + 1) >> 31)) + 1; 
}