C – Determinarea tuturor dacă toți biții pari sunt setați la 1 (Programare, C, Manipulare De Biți, Puzzle)

mrQWERTY a intrebat.

Determină dacă toți biții de loc par (numărând de la stânga la dreapta) sunt setați la 1. De exemplu, 0101 0101 ar conta în timp ce 1011 1000 nu ar conta.

Dacă bitul are 1 în toate locurile pare, returnează 1, altfel returnează 0.

Constrângeri: trebuie să utilizeze numai operatori de tip bitwise. Nu se pot utiliza condiționale. Cel mai mare număr întreg pe care îl puteți utiliza într-o expresie este 0xFF.

Iată codul meu:

int allEvenBits(int X) {
    int x1 = !((X & 0x55) ^ 0x55);
    int x2 = !(((X >> 8) & 0x55) ^ 0x55);
    int x3 = !(((X >> 16) & 0x55) ^ 0x55);
    int x4 = !(((X >> 24) & 0x55) ^ 0x55);
    return x1 + x2 + x3 + x4;

}

Textul de mai sus returnează 1 pentru următoarele: 1011 0010 1001 0010 1011 1001 1111 1111

Cum pot modifica acest lucru pentru a face să funcționeze cu constrângerea?

Comentarii

  • Ce se întâmplă cu 1111 1111? adică, contează biții impari? –  > Por dawg.
  • @dawg biții impari nu contează, așa că asta ar conta. –  > Por mrQWERTY.
  • @barakmanos Nu pot folosi numere întregi mai mari de 0xFF –  > Por mrQWERTY.
3 răspunsuri
rici

Presupunând că >> contează ca un operator bitwise, următoarele au nevoie doar de constante până la 16.

int allEven(unsigned x) {
  x &= x >> 16;
  x &= x >> 8;
  x &= x >> 4;
  x &= x >> 2;
  return x&1;
}

Comentarii

  • Aceasta este o soluție foarte frumoasă și funcționează perfect. Sunt începător în C. Dacă nu vă supărați, puteți explica cum funcționează această logică? Mai exact, nu înțeleg ce fac operatorii &=. –  > Por mrQWERTY.
  • x &= x >> 16 este o prescurtare (valabilă în C) pentru x = x & (x >> 16) . În același mod x += 5 este la fel ca x = x + 5 –  > Por Michael Petch.
  • Tot nu înțeleg cum funcționează, mai ales de ce trebuie să numere doar 16? – user6288471
  • @SittingBull: Nu este chiar o numărare; este mai degrabă o expansiune binară. Fiecare dintre declarații, pe rând, rupe efectiv numărul întreg în două și combină cele două jumătăți cu un bitwise and. Deci, dacă începeți cu 32 de biți (presupunerea), atunci prima jumătate este de 16 biți de la capăt. –  > Por rici.
Michael Graczyk

Presupunând sizeof(int) == 4:

int all_even(int x) {
    int all_even = (0x55<<24)|(0x55<<16)|(0x55<<8)|0x55;
    return x == ((x & ~all_even) | all_even);
}

Se citește ca „Dacă așez toți biții pari în x, noul număr este același cu x?”

Comentarii

  • Nu sunt sigur. == ar fi permis. –  > Por Michael Petch.
Deduplicator

Utilizați bit-shifting și bitwise-and:

int f(unsigned x) {
  x&= x>>16;
  x&= x>>8;
  x&= x>>4;
  x&= x>>2;
  return x&1;
}

Dacă am avea constante mai mari, acest lucru ar fi cel mai bine:

int f(unsigned x) {const unsigned mask = 0x55555555; return mask == (mask&x);}

Comentarii

  • Nu am dat downvote, dar întrebarea specifică faptul că cea mai mare constantă pe care ai voie să o folosești este 0xFF –  > Por user3386109.
  • @user3386109: Am văzut această restricție prea târziu, deși a fost schimbată atunci. –  > Por Deduplicator.
  • Da, aceasta este una dintre acele întrebări stupide de puzzle care necesită o soluție suboptimală, fără un motiv anume. –  > Por user3386109.