XOR programowanie logiczna rada

Question

Biorąc pod uwagę długi int x, policzyć wartości które spełniają następujące warunki:

XORx>x
a < x

gdzie i x są długie liczby całkowite i XOR jest bitowego operatora XOR

Jak byś go o ukończeniu tego problemu?

Powinienem również wspomnieć, że wejście x może być tak duży, jak 10^10

udało mi się dostać brute force rozwiązania przez iteracji ponad 0 do x sprawdzania warunków i zwiększając wartość licznika .. jednak nie jest to optymalne rozwiązanie ...

jest to brute force, że próbowałem. Działa, ale jest bardzo wolny dla dużych wartości x.

for(int i =0; i < x; i++) 
{ 
     if((0 < i && i < x) && (i^x) > x) 
      count++;  
} 

Answer 1

long long NumberOfA(long long x) 
{ 
    long long t = x <<1; 
    while(t^(t&-t)) t ^= (t&-t); 
    return t-++x; 
} 


long long x = 10000000000; 
printf("%lld ==> %lld\n", 10LL, NumberOfA(10LL)); 
printf("%lld ==> %lld\n", x, NumberOfA(x)); 

wyjściowy

10 ==> 5 
10000000000 ==> 7179869183 

Link to IDEOne Code

---

Próba wyjaśnienia logikę (przy użyciu przykład 10 lub 1010b)

• Przesunięcie x lewej 1. (wartość 20 lub 10100b)
• wyłączyć wszystkie niskich bitów, pozostawiając tylko bitem (wartość 16 lub 10000b)
• odejmowania x + 1 (16 - 11 == 5)

---

Próbując wyjaśnić
(chociaż to nie jest łatwe)

Twoja reguła jest taka, że ​​a^x musi być większa niż x, ale nie można dodać dodatkowych bitów do a ani x.
(Jeśli zaczniesz o wartości 4-bitowe, można użyć tylko 4 bity)

Największą możliwą wartość dla liczby w n-bitów jest 2^n -1.
(numer np. 4-bitowy, 2^4-1 == 15)
Umożliwia ten numer B.

Między swojej wartości x i B (włącznie), istnieje B - x możliwych wartości.
(z powrotem do przykładu, 10. Między 15 i 10, nie jest 5 możliwe wartości: 11, 12, 13, 14, 15)

w kodzie, t jest x << 1, a następnie wszystkie niskie bity wyłączone.
(10 << 1 jest 20; wyłączyć wszystkie niskie bity dostać 16)

Następnie 16 - 1 jest B i B - x jest odpowiedź:
(t - 1 - x, jest taka sama jak t - ++x , jest odpowiedzią)

Answer 2

Jednym ze sposobów obejrzenia tego jest rozważenie każdego z bitów w x.

• Jeśli jest 1, to odwrócenie spowoduje mniejszą liczbę.
• Jeśli jest 0, to odwrócenie spowoduje większą liczbę, a my powinniśmy ją policzyć - a także wszystkie kombinacje bitów po prawej. To wygodnie sumuje się z wartością maski.

long f(long const x) 
{ 
    // only positive x can have non-zero result 
    if (x <= 0) return 0; 

    long count = 0; 

    // Iterate from LSB to MSB 
    for (long mask = 1; mask < x; mask <<= 1) 
     count += x & mask 
      ? 0 
      : mask; 

    return count; 
} 

Możemy podejrzewać, wzór tutaj - wygląda na to, jesteśmy po prostu kopiując x i przerzucanie jego bitów. Potwierdź

Let, wykorzystując minimalną program testowy:

#include <cstdlib> 
#include <iostream> 

int main(int, char **argv) 
{ 
    while (*++argv) 
     std::cout << *argv << " -> " << f(std::atol(*argv)) << std::endl; 
} 

0 -> 0 
1 -> 0 
2 -> 1 
3 -> 0 
4 -> 3 
5 -> 2 
6 -> 1 
7 -> 0 
8 -> 7 
9 -> 6 
10 -> 5 
11 -> 4 
12 -> 3 
13 -> 2 
14 -> 1 
15 -> 0 

Więc wszystko co musimy zrobić, to „rozmaz” wartość tak, że wszystkie bity zerowe po najbardziej znaczącego 1 są ustawione, następnie XOR z tym:

long f(long const x) 
{ 
    if (x <= 0) return 0; 
    long mask = x; 
    while (mask & (mask+1)) 
     mask |= mask+1; 
    return mask^x; 
} 

To jest znacznie szybsze i nadal O (log n).