IT şi electronică > Programare
problema cu operatii pe biti
AlexandruLazar:
Mă bucur să te văd din nou pe aici, Adi :).
Ideea pe care ai amintit-o e una foarte utilă. Ca să o explic mai pe larg, ea constă în a atribui fiecărui bit dintr-un număr o anumită semnificație. De exemplu, dacă primul bit este setat (are valoarea 1), asta poate însemna că evenimentul a trecut primul criteriu; dacă al doilea este setat, că l-a trecut pe al doilea ș.a.m.d.. Se poate face asta folosind operațiile AND, OR și NOT.
Avantajul principal al acestei soluții constă în consumul scăzut de memorie. Cel mai recent am folosit asta într-un program care trebuie, între altele, să rețină la ce clase de comenzi pot răspunde o serie de dispozitive aflate într-o rețea wireless -- fiecare bit reprezentând faptul că dispozitivul are anumite capacități (de exemplu că este un dimmer de lumini, deci poate răspunde la comenzile unuia și poate fi inclus într-un anumit fel într-un program de economisire a energiei). Sunt 6 clase de comenzi posibile, deci încap toate într-un byte. La prima vedere nu e mare lucru 1 byte în loc de 6, dar în rețea pot fi până la 256 dispozitive iar spațiul total pe care îl avem la dispoziție pentru stocarea acestor informații este de 2K. În felul acesta, putem stoca clasele de comenzi în numai 256 de bytes pentru toate dispozitivele din rețea. Dacă fiecare ar fi avut o variabilă separată, sau un element dintr-un vector, am fi depășit spațiul alocat.
Adi:
Si eu ma bucur sa revin, Alex. Asa e, tehnica e foarte utila, interesant exemplul oferit de tine. As adauga insa ca mai e comanda foarte utila, pe langa AND, OR, NOT, si anume XOR.
Astfel, daca avem o lista de criterii de selectie, unul independent de altul.
A = lista de criterii pe care le dorim sa le folosim in principiu
ex: A = 11 (toate criteriile vor fi folosite) ex: daca copilul fumeaza sau nu; apoi daca a luat bacul sau nu)
ex: A = 01 (un criteriu nu va fi folosit, anume daca copilul fumeaza, astfel copiii vor fi selectati indiferent daca fumeaza sau nu)
B = lista de ce trebuie sa indeplineasca pentru fiecare criteriu, unde 0 inseamna ca vreau ca acel criteriu sa fie picat de copilul ca sa il selectez pentru un premiu (ex: vreau un copil care sa NU fumeze) si 1 vreau ca acel criteriu sa fie trecut de (ex: vreau un copil care sa fi luat bacul).
deci B = 01
Astea doua sunt valabile pentru toti copiii. Acum pentru fiecare copil in parte completam efectiv daca a trecut sau nu fiecare criteriu posibil.
C = 11 (fumeaza si a luat bacul)
C = 10 (fumeaza si a picat bacul)
C = 01 (nu fumeaza si a luat bacul)
C = 00 (nu fumeaza si a picat bacul)
Bun, acum daca vreau sa verific pentru fiecare copil daca a trecut de selectiile mele sau nu calculez.
(NOT A) OR (XOR(B,C))
Vedem cum intervine XOR si el e cheia. Rezultatul va avea acelasi numar de biti. Copilul a trecut toate criteriile daca toti bitii sunt unu (11). Daca cel putin unul din ei e zero, copilul nu a trecut toate criteriile pe care le doresc.
Eu am verificat matematic formula pentru 1 sau 2 biti in criterii. Am facut efectiv toate combinatiile. Pentru 3 sau mai multe nu stiu matematic daca merge, dar avem un cod care verifica asta bit cu bit, iar nu intr-o singura formula, asadar voi putea compara formula mea cu codul acela. Si daca formula chiar e corecta pentru orice numar de biti, atunci putem simplifica acel cod cu doar aceasta formula. Dar intai trebuie sa o implementez in C++.
Acum sarcina mea pentru cercetare, intre altele, e sa fac un program in C++ care sa ia aceste trei numere care pot avea foarte multi biti, gen vreo 20 sau 30, si sa imi dea un 0 sau 1 in functie de A, B, C.
ex:
A=1010111111111
B=1110011101110
un eveniment cu
C=1011111101100
Mai e o etapa intermediara, caci numerele A, B, C vor fi date in baza 10, nu in baza 2, si trebuei convertite intai in baza 2.
Si raspunsul sa fie 0 sau 1, true sau false.
Avem o idee, dar inca nu am implementat-o, caci saptamana asta pregatesc o conferinta. Dar idei de aici sunt binevenite. Mersi mult.
AlexandruLazar:
Cum adică numerele vor fi în baza de date în baza 10? Sunt stocate sub formă de text, sau...?
MariS:
--- Citat din: Adi din Iulie 16, 2012, 12:18:26 p.m. ---Si eu ma bucur sa revin, Alex. Asa e, tehnica e foarte utila, interesant exemplul oferit de tine. As adauga insa ca mai e comanda foarte utila, pe langa AND, OR, NOT, si anume XOR.
Astfel, daca avem o lista de criterii de selectie, unul independent de altul.
A = lista de criterii pe care le dorim sa le folosim in principiu
ex: A = 11 (toate criteriile vor fi folosite) ex: daca copilul fumeaza sau nu; apoi daca a luat bacul sau nu)
ex: A = 01 (un criteriu nu va fi folosit, anume daca copilul fumeaza, astfel copiii vor fi selectati indiferent daca fumeaza sau nu)
B = lista de ce trebuie sa indeplineasca pentru fiecare criteriu, unde 0 inseamna ca vreau ca acel criteriu sa fie picat de copilul ca sa il selectez pentru un premiu (ex: vreau un copil care sa NU fumeze) si 1 vreau ca acel criteriu sa fie trecut de (ex: vreau un copil care sa fi luat bacul).
deci B = 01
Astea doua sunt valabile pentru toti copiii. Acum pentru fiecare copil in parte completam efectiv daca a trecut sau nu fiecare criteriu posibil.
C = 11 (fumeaza si a luat bacul)
C = 10 (fumeaza si a picat bacul)
C = 01 (nu fumeaza si a luat bacul)
C = 00 (nu fumeaza si a picat bacul)
Bun, acum daca vreau sa verific pentru fiecare copil daca a trecut de selectiile mele sau nu calculez.
(NOT A) OR (XOR(B,C))
Vedem cum intervine XOR si el e cheia. Rezultatul va avea acelasi numar de biti. Copilul a trecut toate criteriile daca toti bitii sunt unu (11). Daca cel putin unul din ei e zero, copilul nu a trecut toate criteriile pe care le doresc.
Eu am verificat matematic formula pentru 1 sau 2 biti in criterii. Am facut efectiv toate combinatiile. Pentru 3 sau mai multe nu stiu matematic daca merge, dar avem un cod care verifica asta bit cu bit, iar nu intr-o singura formula, asadar voi putea compara formula mea cu codul acela. Si daca formula chiar e corecta pentru orice numar de biti, atunci putem simplifica acel cod cu doar aceasta formula. Dar intai trebuie sa o implementez in C++.
Acum sarcina mea pentru cercetare, intre altele, e sa fac un program in C++ care sa ia aceste trei numere care pot avea foarte multi biti, gen vreo 20 sau 30, si sa imi dea un 0 sau 1 in functie de A, B, C.
ex:
A=1010111111111
B=1110011101110
un eveniment cu
C=1011111101100
Mai e o etapa intermediara, caci numerele A, B, C vor fi date in baza 10, nu in baza 2, si trebuei convertite intai in baza 2.
Si raspunsul sa fie 0 sau 1, true sau false.
Avem o idee, dar inca nu am implementat-o, caci saptamana asta pregatesc o conferinta. Dar idei de aici sunt binevenite. Mersi mult.
--- Terminare citat ---
Adi, iti dau o idee, ca aici ar trebui sa ma mai pricep, fiind in domeniu: foloseste masti pe biti. Exemplu:
#define MASK_Criteriu_1 1
#define MASK_Criteriu_2 2
#define MASK_Criteriu_3 4
#define MASK_Criteriu_4 8
#define MASK_Criteriu_5 16
#define MASK_Criteriu_6 32
..............................
#define MASK_Criteriu_32 2**31
si o variabila Criterii_indeplinite pe care o poti incarca simplu cu criteriile indeplinite:
Criterii_indeplinite = MASK_Criteriu_3 | MASK_Criteriu_5 | MASK_Criteriu_7;
iar daca vrei sa scoti un criteriu, de ex. criteriul 5, folosesti expresia:
Criterii_indeplinite &= (~MASK_Criteriu_5);
si variabila va contine doar criteriul 3 si 7.
Poti folosi inca o variabila, numita Etalon_Criterii_Particula_X si o initializezi cu criteriile pe care trebuie sa le indeplineasca particula x, de ex:
Etalon_Criterii_Particula_X = MASK_C1 | MASK_C4 | MASK_C6 | ... |MASK_C29;
si variabila Criterii_indeplinite o folosesti ca variabila de lucru, actualizand-o cu fiecare criteriu indeplinit de particula X. La final folosesti formula:
Particula_X_confirmata = (Etalon_Criterii_Particula_X == Criterii_indeplinite? TRUE: FALSE);
Daca te mai pot ajuta, cu placere.
Adi:
Multumesc, o sa incerc si o sa revin.
Navigare
Du-te la versiunea completă