Cum pot inversa biții ON într-un octet?

Citeam cartea lui Joel, unde sugera ca întrebare de interviu:

Scrieți un program pentru a inversa biții "ON" într-un octet dat.

Mă gândesc doar la o soluție folosind C.

Solicitând aici, astfel încât să puteți să-mi arătați cum să faceți într-un mod non-C (dacă este posibil)

0
fr hi bn
XOR împotriva tuturor celor 1.
adăugat autor Brad Wilson, sursa

17 răspunsuri

Și aici este o versiune direct tăiată și lipită de la OpenJDK , care este interesantă deoarece nu implică nicio buclă. Pe de altă parte, spre deosebire de versiunea de program pe care am postat-o, această versiune funcționează numai pentru numerele de 32 și 64 de biți. :-)

Versiune pe 32 de biți:

public static int reverse(int i) {
   //HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

64-bit versiune:

public static long reverse(long i) {
   //HD, Figure 7-1
    i = (i & 0x5555555555555555L) << 1 | (i >>> 1) & 0x5555555555555555L;
    i = (i & 0x3333333333333333L) << 2 | (i >>> 2) & 0x3333333333333333L;
    i = (i & 0x0f0f0f0f0f0f0f0fL) << 4 | (i >>> 4) & 0x0f0f0f0f0f0f0f0fL;
    i = (i & 0x00ff00ff00ff00ffL) << 8 | (i >>> 8) & 0x00ff00ff00ff00ffL;
    i = (i << 48) | ((i & 0xffff0000L) << 16) |
        ((i >>> 16) & 0xffff0000L) | (i >>> 48);
    return i;
}
0
adăugat

Întrucât întrebarea a cerut un mod non-C, iată o implementare a Schemei, plăcută cu plăcere de la SLIB :

(define (bit-reverse k n)
  (do ((m (if (negative? n) (lognot n) n) (arithmetic-shift m -1))
       (k (+ -1 k) (+ -1 k))
       (rvs 0 (logior (arithmetic-shift rvs 1) (logand 1 m))))
      ((negative? k) (if (negative? n) (lognot rvs) rvs))))

(define (reverse-bit-field n start end)
  (define width (- end start))
  (let ((mask (lognot (ash -1 width))))
    (define zn (logand mask (arithmetic-shift n (- start))))
    (logior (arithmetic-shift (bit-reverse width zn) start)
            (logand (lognot (ash mask start)) n))))

Rescrisă ca C (pentru persoanele care nu cunosc Schema), ar arăta așa (cu înțelegerea faptului că în Schemă numerele pot fi arbitrar de mari):

int
bit_reverse(int k, int n)
{
    int m = n < 0 ? ~n : n;
    int rvs = 0;
    while (--k >= 0) {
        rvs = (rvs << 1) | (m & 1);
        m >>= 1;
    }
    return n < 0 ? ~rvs : rvs;
}

int
reverse_bit_field(int n, int start, int end)
{
    int width = end - start;
    int mask = ~(-1 << width);
    int zn = mask & (n >> start);
    return (bit_reverse(width, zn) << start) | (~(mask << start) & n);
}
0
adăugat
Probabil că am greșit, dar eu   a crezut că întrebarea lui Joel a fost despre   numărați biții "pe" mai degrabă decât   inversarea acestora.

Poftim:

#include 

int countBits(unsigned char byte);

int main(){
  FILE* out = fopen( "bitcount.c" ,"w");

  int i;
  fprintf(out, "#include \n#include \n#include \n\n");

  fprintf(out, "int bitcount[256] = {");
  for(i=0;i<256;i++){
    fprintf(out, "%i", countBits((unsigned char)i));
    if( i < 255 ) fprintf(out, ", ");
  }
  fprintf(out, "};\n\n");

  fprintf(out, "int main(){\n");

  fprintf(out, "srand ( time(NULL) );\n");
  fprintf(out, "\tint num = rand() %% 256;\n");
  fprintf(out, "\tprintf(\"The byte %%i has %%i bits set to ON.\\n\", num, bitcount[num]);\n");

  fprintf(out, "\treturn 0;\n");
  fprintf(out, "}\n");
  fclose(out);

  return 0;
}

int countBits(unsigned char byte){
  unsigned char mask = 1;
  int count = 0;
  while(mask){
    if( mask&byte ) count++;
    mask <<= 1;
  }
  return count;
}
0
adăugat

Inversarea ordinii de biți în C #:

byte ReverseByte(byte b)
{
    byte r = 0;
    for(int i=0; i<8; i++)
    {
        int mask = 1 << i;
        int bit = (b & mask) >> i;
        int reversedMask = bit << (7 - i);
        r |= (byte)reversedMask;
    }
    return r;
}

Sunt sigur că există modalități mai inteligente de a face acest lucru, dar în acest caz precis, întrebarea pentru interviu este menită să determine dacă știți operațiuni bitwise, deci cred că această soluție ar funcționa.

Într-un interviu, intervievatorul vrea, de obicei, să știe cum găsești o soluție, care ești abilitățile de rezolvare a problemelor, dacă e curat sau dacă e un hack. Deci, nu veniți cu o soluție prea inteligentă, deoarece probabil că înseamnă că ați găsit-o undeva pe Internet în prealabil. Nu încercați să falsificați faptul că nici tu nu știți și că tocmai ați venit cu răspunsul pentru că sunteți un geniu, acest lucru va fi chiar și mai rău dacă se va dovedi din moment ce minți.

0
adăugat

Ce înseamnă în mod specific această întrebare?

Are inversă înseamnă setarea 1 la 0 și invers?

Or does it mean 00001100 --> 00110000 where you reverse their order in the byte? Or perhaps just reversing the part that is from the first 1 to the last 1? ie. 00110101 --> 00101011?

Presupunând că aceasta înseamnă inversarea ordinii de biți în întreg octetul, iată o versiune de asamblare x86:

; al is input register
; bl is output register

xor bl, bl      ; clear output

; first bit
rcl al, 1       ; rotate al through carry
rcr bl, 1       ; rotate carry into bl

; duplicate above 2-line statements 7 more times for the other bits

nu soluția cea mai optimă, o căutare de tabel este mai rapidă.

0
adăugat

Ce anume înseamnă această întrebare?

Buna intrebare. Dacă inversarea biților "ON" înseamnă inversarea numai a biților care sunt "ON", veți primi întotdeauna 0, indiferent de intrare. Dacă aceasta înseamnă inversarea tuturor biților, adică schimbarea tuturor celor 1s la 0s și a tuturor celor 0s la 1s, așa cum l-am citit inițial, atunci este doar un NOT sau un complement bitus. Limbile bazate pe C au un operator de completare, ~ , care face acest lucru. De exemplu:

unsigned char b = 102;      /* 0x66, 01100110 */
unsigned char reverse = ~b; /* 0x99, 10011001 */
0
adăugat

Pagina clasică Bit Hacks are mai multe moduri (într-adevăr foarte inteligente) de a face acest lucru, dar este tot în C. Orice limbă derivată din sintaxa C (în special Java) va avea probabil metode similare. Sunt sigur că vom obține câteva versiuni Haskell în acest thread;)

0
adăugat

byte ReverseByte (octetul b)   {       retur b ^ 0xff;   }

Funcționează dacă ^ este XOR în limba dvs., dar nu și dacă este AND , adesea este.

0
adăugat

Dacă vorbim despre trecerea lui 1 în 0 și 0 la 1, folosind Ruby:

n = 0b11001100
~n

Dacă intenționați să inversați ordinea:

n = 0b11001100
eval("0b" + n.to_s(2).reverse)

Dacă intenționați să numărați biți, așa cum au menționat un alt utilizator:

n = 123
count = 0
0.upto(8) { |i| count = count + n[i] }

? Rubin

0
adăugat

pseudo cod..

while (Read())
  Write(0);
0
adăugat

Inversarea biților. De exemplu, avem un număr reprezentat de 01101011. Acum, dacă vom inversa biții, atunci acest număr va deveni 11010110. Acum, pentru a realiza acest lucru, ar trebui să știți mai întâi cum să faceți schimbarea a două biți într-un număr. Schimbând doi biți într-un număr: - XOR ambele biți cu unul și a vedea dacă rezultatele sunt diferite. Dacă nu sunt atunci ambii biți sunt aceiași altfel XOR ambii biți cu XOR și salvați-l în numărul său original; Acum pentru inversarea numărului PENTRU I mai puțin decât Numberofbits/2    de swap (număr, I, NumberOfBits-1-I);

0
adăugat

Eu spun întrebare truc. :) Inversarea tuturor biților înseamnă un flip-flop, dar numai biții care sunt în mod clar înseamnă:

return 0;
0
adăugat

Iată Soln obligatoriu Haskell pentru completarea biților, folosește funcția de bibliotecă, se completează:

import Data.Bits
import Data.Int

i = 123::Int
i32 = 123::Int32
i64 = 123::Int64
var2 = 123::Integer

test1 = sho i
test2 = sho i32
test3 = sho i64
test4 = sho var2 -- Exception

sho i = putStrLn $ showBits i ++ "\n" ++ (showBits $complement i)
showBits  v = concatMap f (showBits2 v) where
   f False = "0"
   f True  = "1"
showBits2 v = map (testBit v) [0..(bitSize v - 1)]
0
adăugat

Solicitați aici, pentru a putea să-mi arăți cum să procedați într-un mod Non C (dacă este posibil)

Spuneți că aveți numărul 10101010. Pentru a schimba 1s la 0s (și invers), trebuie să utilizați XOR:

 10101010
^11111111
 --------
 01010101

Făcând-o manuală este cam așa "non-C", așa cum veți obține.

Cu toate acestea, din formularea întrebării se pare că este doar numai dezactivând biții "ON" ... În acest caz răspunsul este zero (după cum sa menționat deja anterior) (cu excepția cazului în care, desigur, întrebarea este de fapt, cererea de a schimba ordinea biților).

0
adăugat

Dacă întrebarea înseamnă să răsturnați toți biți și nu vi se permite să utilizați operatori de tip C, cum ar fi XOR și NOT, atunci acest lucru va funcționa:

bFlipped = -1 - bInput;
0
adăugat

Probabil că am greșit, dar m-am gândit că întrebarea lui Joel se referea la numărarea biților "pe" decât la inversarea lor.

0
adăugat

Aș modifica al doilea exemplu al lui Palmsey, eliminând o eroare și eliminând eval :

n = 0b11001100
n.to_s(2).rjust(8, '0').reverse.to_i(2)

Codul rjust este important dacă numărul care urmează să fie inversat pe biți este un câmp de bit cu lungime fixă ​​- fără el, inversul 0b00101010 va fi 0b10101 < cod> mai degrabă decât codul 0b01010100 corect. (Evident, cele 8 ar trebui să fie înlocuite cu lungimea în cauză). Tocmai m-am împiedicat de asta.

0
adăugat