BitCell

by **eni4ever** » 22 Jun 2011, 02:19

"tl;dr" fans beware: upon reading this post, a 1.5 grams loss in saliva fluids is guaranteed!

Sume defecte [Să-nvățăm când concurăm]

Prolog:
VeveritaCuPedale, un utilizator stimat de altfel de la noi din comunitate, s-a gândit el într-o zi că ar fi tare dacă ar înțelege cum funcționează adunarea într-un procesor. Destinul sau poate chiar bookmark-ul pus pe bitcell i-a adus parte din răspuns chiar aici pe forum.
Parcurgând explicațiile, Veve este supărat : tabelul nu este complet! "Cum este influențată suma unui bit în funcție de restul operației de adunare din rangurile precedente ?" Se întrebă el.
Fiind o fire conștiincioasă și perseverentă, Veve reușește să-și completeze singur tabelul :

Coloanele colorate în albastru reprezintă intrări pentru celula de adunare, iar coloanele colorate în verde - ieșiri.
Pentru a înțelege mai bine celula, Veve s-a apucat să îi dea și o formă care să îmbrace logica și a ajuns la această desen frumos :

Partea frumoasă, așa cum a considerat-o și activistul nostru mic, a fost reușita lui de a sintetiza, pe cât l-a dus căpușorul, cele 2 funcții care modelează comportamentul celulei de adunare :

Rezultatul operațiunii de adunare: $z_i=(\neg x_i * y_i * \neg r_{intrare}) + (x_i * \neg y_i * \neg r_{intrare}) + (\neg x_i * \neg y_i * r_{intrare}) + (x_i * y_i * r_{intrare})$
Restul adunării : $r_{iesire}=(x_i * y_i * \neg r_{intrare}) + (\neg x_i * y_i * r_{intrare}) + (x_i * \neg y_i * r_{intrare}) + (x_i * y_i * r_{intrare})$

[S-a notat cu $\neg$ - negarea unui termen. Spre exemplu $\neg a$ este 1 dacă și numai dacă a = 0 și este 0 dacă a = 1, etc.]

Pe baza acestor funcții și folosind o serie de porți logice, Veve a reușit să creeze circuistica unei astfel de celule sumator :
Pentru calculul bitului de sumă $z_i$ , schema electrică rezultată a fost :

Pentru calculul bitului de rest $r_{iesire}$ care se va propaga la următorul rang, schema electrică a fost :

Încapsulând cele 2 circuite în diagrama condensată prezentată sub tabel și multiplicând celula, Veve a reușit într-un final să creeze un sumator pe 16 biți. Modul în care a interconectat cele 16 celule a fost, după cum se observă, în serie :

La testarea sumatorului însă, buba! : stimatul nostru colocatar a observat că ceva nu funcționează așa cum ar trebui. Îi dăm o mână de ajutor să descopere ce anume ?

Descrierea problemei:
Tot ce speculează Veve este că, datorită porților logice vechi recuperate dintr-un calculator ponosit, sigur o poartă este defectă și, în consecință, scoate aceeași valoare logică indiferent de valorile prezente la intrările sale, stricând astfel rezultatul final. Problema este că Veve nu știe nici în care celulă se află poarta buclucașă și nici ce afectează ea (suma sau restul). El are doar niște date de analiză rezultate în urma testării unor valori prin sumator și observând rezultatul.

Ajutați-l pe Veve să descopere poarta buclucașă și demonstrați că ați găsit-o printr-o aplicație care preia 2 numere de maxim 16 biți dintr-un fișier și, în urma procesării, scrie rezultatul obținut de Veve în alt fișier.

Date de analiză:
X = 5; Y = 13 => suma_veve(X, Y) = 50
X = 47; Y = 67 => suma_veve(X, Y) = 114 (fiind mereu setat, uneori suma este corectă)
X = 925; Y = 379 => suma_veve(X, Y) = 1336
X = 30439; Y = 17583 => suma_veve(X, Y) = 48054
X = 49151; Y = 55159 => suma_veve(X, Y) = 38774 (trunchere de rezultat la primii 16 biți)

Date de intrare:
Fișierul "bitcell10.in" conține, separate printr-un spațiu, cele 2 numere naturale X și Y de maxim 16 biți cu semnificația de mai sus.

Date de ieșire:
În "bitcell10.out" : Un singur număr, rezultatul sumatorului lui Veve aplicat pe X și Y-ul citit mai sus. Datorită limitărilor fizice, în caz de situație de overflow ( suma_veve(X, Y) nu încap pe 16 biți), rezultatul se va trunchea la cei mai puțini semnificativi 16 biți!

Exemplu:
"bitcell10.in" : 17 4
"bitcell10.out" : 53

Bonus:
Numerele din fișierul de intrare sunt scrise în baza 10, dar frecvent ... în circuistică, se lucrează pentru claritate, direct cu baza 2. Pentru a interpreta corect baza-non-zecimală a unui număr se folosesc, de regulă, prefixe. Astfel, binar-ul are prefixul "0b". În această idee, ca și bonus, construiți aplicația să poată citi numerele din fișierul de intrare atât în baza implicit 10 cât și în baza 2 (condiționat de prezența prefixului, desigur).

Exemplu bonus:
"bitcell10.in" : 0b1101 12
este totuna cu
"bitcell10.in" : 13 12
deoarece 13 = 1101 (în baza 2)
sau
"bitcell10.in" : 0b0001010 0b100001
este totuna cu
"bitcell10.in" : 10 33

Vă mulțumesc pentru atenție,
Game on!

P.S: Pentru alte date de analiză/nedumeriri, vă rog folosiți forumul.

Perioada de desfășurare:
22-30 Iunie - înscrierea în concurs
1 Iulie - desemnarea câștigătorului

by **Mihai** » 22 Jun 2011, 04:44

Interesantă problemă, soluția mea o găsiți în atașament.

Dacă vreți să participați, vă rog să-i trimiteți surse lui eni4ever pentru că, din moment ce m-am înscris și eu, n-ar fi prea corect să aleg tot eu câștigătorul

.

by **DarkByte** » 23 Jun 2011, 18:55

E interesanta, intr-adevar ... dar daca-mi pot permite o critica: enuntul e MULT prea lung.

Either way, programul meu e in atasament.

by **eni4ever** » 26 Jun 2011, 23:26

up! că nu este greu, ce dracu? ...

Spor (?!?)

by **smith** » 27 Jun 2011, 14:05

^Aș participa și eu Victore, dar mă stresează bacu'

by **eni4ever** » 01 Jul 2011, 23:59

^ Hai hai, nu mai este bac <-> nu mai este motiv să nu participați! Puteți coda în liniște, zic eu ...

Voi aștepta (cu folos, sper) până în ultimul moment înainte să închei concursul (undeva pe la 11:59) și să desemnez un câștigător.

Spor

L.E. (-- 01 Jul 2011, 22:59 --)

Oh well ... se pare că numai 2 participanți avem.

Amândouă soluții :
DarkByte:

Line number On/Off | Expand/Contract | Select all

program bitcell_10;
 
{$APPTYPE CONSOLE}
 
// SysUtils - begin
function ExtractFilePath(const FileName: string): string;
var
  i: Integer;
begin
  for i := Length(FileName) downto 1 do
    if (FileName[i] = '')
      then Break;
 
  Result := Copy(FileName, 1, I);
end;
 
function Trim(const S: string): string;
var
  I, L: Integer;
begin
  L := Length(S);
  I := 1;
  while (I <= L) and (S[I] <= ' ') do
    Inc(I);
 
  if (I > L)
    then Result := ''
    else
      begin
        while S[L] <= ' ' do Dec(L);
        Result := Copy(S, I, L - I + 1);
      end;
end;
 
function StrToIntDef(const S: string; Default: Integer): Integer;
var
  E: Integer;
begin
  Val(S, Result, E);
  if E <> 0 then Result := Default;
end;
// SysUtils - end
 
function BinToDec(aBinaryValue: String): Integer;
var
  lIndex: Integer;
begin
  Result := 0;
 
  for lIndex := 1 to Length(aBinaryValue) do
    if (aBinaryValue[lIndex] = '1')
      then Break;
  if (lIndex > 0)
    then aBinaryValue := Copy(aBinaryValue, lIndex, Length(aBinaryValue));
 
  for lIndex := Length(aBinaryValue) downto 1 do
   if (aBinaryValue[lIndex] = '1')
     then Result := Result + (1 shl (Length(aBinaryValue) - lIndex));
end;
 
function GetNumber(aString: String): Word;
begin
  aString := Trim(aString);
 
  if (Pos('b', aString) > 0) or ((Pos('B', aString) > 0))
    then Result := BinToDec(aString)
    else Result := StrToIntDef(aString, 0);
end;
 
procedure GetNumbers(aInputLine: String; var a, b: Word);
var
  lIndex: Integer;
  lFoundDigit: Boolean;
begin
  lFoundDigit := False;
  for lIndex := 1 to Length(aInputLine) do
    begin
      if (aInputLine[lIndex] in ['0' .. '9', 'b', 'B'])
        then lFoundDigit := True
        else
          if lFoundDigit
            then Break;
    end;
 
  a := GetNumber(Copy(aInputLine, 1, lIndex - 1));
  b := GetNumber(Copy(aInputLine, lIndex + 1, Length(aInputLine)));
end;
 
function WrongSum(a, b: Word): Word;
begin
  Result := 32 or (a + b);
end;
 
const
  InputFile = 'bitcell10.in';
  OutputFile = 'bitcell10.out';
 
var
  AppPath, lInput, lTemp: String;
  fInput, fOutput: TextFile;
  a, b: Word;
 
begin
  AppPath := ExtractFilePath(ParamStr(0));
  AssignFile(fInput, AppPath + InputFile);
  Reset(fInput);
 
  lInput := '';
  while not EoF(fInput) do
    begin
      ReadLn(fInput, lTemp);
      lInput := lInput + ' ' + lTemp;
    end;
  CloseFile(fInput);
 
  GetNumbers(lInput, a, b);
 
  AssignFile(fOutput, AppPath + OutputFile);
  Rewrite(fOutput);
  Write(fOutput, WrongSum(a, b));
  CloseFile(fOutput);
end.

Mihai:

Line number On/Off | Expand/Contract | Select all

#include <cstdio>
#include <cstring>
#include <cstdlib>
 
//citim un numar in baza 2 sau 10 si returnam echivalentul in baza 10
//presupune ca numerele din baza 2 au un singur 0 in prefix - deci 00b10 nu este valid, pe cand 0b10 este
int citire()
{
    char sNumar[19];
    scanf("%s",&sNumar);
    if(strlen(sNumar)>=3&&sNumar[1]=='b')
        return strtol(sNumar+2,NULL,2);
    else
        return strtol(sNumar,NULL,10);
}
 
int main()
{
    int x,y;
 
    //vrem sa citim si sa afisam in fisier
    freopen("bitcell10.in","r",stdin);
    freopen("bitcell10.out","w",stdout);
 
    //citim cele doua valori
    x=citire();
    y=citire();
 
    //rezolvarea propriu-zisa
    printf("%d\n",(x+y|0x20)&0xffff);
   
    //happy end :)
    return 0;
}

s-au descurcat foarte bine pe testele supuse :

Teste wrote:0 0
1 0
0b01 0
0b10 0b01
0b100 1
0b1111111111111111 0
0b1111111111111111 65535

Sincere felicitări amândurora! Întradevăr, bitul 5 din sumă era cel buclucaș rămânând tot timpul setat pe 1.
Totuși, nu poate existadecât un singur câștigător și acela este ... param-pam-pam
Offtopic
Ceea ce a făcut departajarea a fost LOC-ul codului sugerat precum și eleganța de care a dat dovadă în implementare. Simplu și eficient aș zice!

Concursul s-a încheiat, vă mulțumesc pentru participare și (mai ales) pentru răbdare. Mihai, ai cuvântul cu următorul challenge

.

BitCell

[10] Concurs - Sume defecte

[10] Concurs - Sume defecte

Re: [10] Concurs - Sume defecte

Re: [10] Concurs - Sume defecte

Re: [10] Concurs - Sume defecte

Re: [10] Concurs - Sume defecte

Re: [10] Concurs - Sume defecte

Who is online