problema cu operatii pe biti

[automat]

Salut.

Am gasit o problema pe care sa mor daca o inteleg.
In cazul operatiei pe biti nu inteleg de rezultatul este : 32
i=i<<3 este 8,  mai departe ....
In cazul primului printf daca b=3 ; b++ este 3
                                              b++ este 4
                                              ++b este 6


#include<stdio.h>

int main()
{
    int i=1;
    int a=5, b=3;
    i=i<<3+i<<1;
    printf("\n %d \n", i);
    printf("\n %d %d %d\n", ++a, a++, a++);
    printf("\n %d %d %d\n", b++, b++, ++b);
}

[Pozitron]

@automat: Esti rugat sa pui titluri mai sugestive topicelor deschise aici. Daca mai gasesc topice cu titlul "problema" si atat, le voi muta la cosul de gunoi.

<Pozitron>

[AlexandruLazar]

Rezultatul operaţiilor pe biţi este un caz de precedenţă a operatorilor. Operatorii de deplasare pe biţi (<< şi >>) au prioritate mai mică decât cei aritmetici (+, - etc.), iar asociativitatea lor este de la stânga la dreapta. Astfel încât i = i << 3 + i << 1 se evaluează ca i = ( i << (3 + i) ) << 1 . Operatorul "=" are prioritatea cea mai mică din expresia asta, deci atribuirea se evaluează ultima.

Acum dacă i = 1, înseamnă că avem i = (1 << 4) << 1, deci i = 16 << 1 care dă 32.

Vezi aici (include şi operatorii C, şi cei din C++).

Primul printf e un caz de comportament nedefinit:

When calling a function (whether or not the function is inline), there is a sequence point after the evaluation of all function arguments (if any) which takes place before execution of any expressions or statements in the function body. There is also a sequence point after the copying of a returned value and before the execution of any expressions outside the function.

Un sequence point este un punct din execuţia programului în care este garantat faptul că toate modificările unor variabile datorate unor expresii anterioare au fost efectuate, şi nicio modificare datorată unei expresii care nu a fost încă evaluate nu se află în desfăşurare. De exemplu, în printf("%d", ++a), există un sequence point după evaluarea argumentelor funcţiei ("%d", respectiv ++a), iar apelul este legal şi previzibil -- atunci când execuţia funcţiei printf() începe, e garantat faptul că ++a a fost evaluat iar valoarea lui a a fost schimbată.

Regula pentru ca o operaţie să nu fie ambiguuă este că o variabilă să fie modificată o singura dată între două sequence point-uri. Un apel de tipul printf("%d %d", ++a, a++) este ambiguuă pentru că, deşi există un sequence point după evaluarea argumentelor lui printf, până să ajungi la el încerci de două ori să modifici valoarea lui a. Virgula din apelul unei funcţii nu este operatorul binar ",": ordinea evaluării argumentelor unei funcţii nu este specificată.

Ca idee, la primul printf eu am obţinut "8, 6, 5", iar la al doilea "5, 4, 6".

[Adi]

Ce itneresant ca se dezbate acest subiect aici. Folosim astfel de operatii pe biti in codul nostru in fizica particulelor pentru a putea modela intr-un singur numar (o insiruire de 0 si 1) daca un eveniment (o fotografie de coliziuni de particule) trece sau nu fiecare din insiruirea de criterii dorite pentru selectarea evenimentelor. Si chiar am de facut un programel care sa introduca asta, dupa ce cred ca am gasit o formula draguta saptamana trecuta. Am citit atunci o zi intreaga pe Wikipedia despre operatii pe biti.

http://en.wikipedia.org/wiki/Bitwise_operation

[MariS]

    int i=1;
    int a=5, b=3;
    i=i<<3+i<<1;
    printf("\n %d \n", i);
    printf("\n %d %d %d\n", ++a, a++, a++);
    printf("\n %d %d %d\n", b++, b++, ++b);

Corect raspunsul lui Alexandru Lazar. Eu am primit un rezultat un pic diferit:
32
8 6 5
5 4 4
Cu 32 s-a lamurit foarte bine de Alexandru. De ce 8 6 5? Se observa ca argumentele au fost evaluate de la dreapta la stanga: ultimul argument este postincrementat, deci se printeaza cu vechea valoare, adica 5, apoi se incrementeaza si devine 6. Argumentul mijlociu e tot postincrementat, dar fiind evaluat dupa cel ultim va primi valoarea incrementata de la acesta, adica 6, si pe asta o printeaza, dupa care o incrementeaza si el, valoarea lui "a" devenind 7. Iar primul argument, fiind preincrementat, ridica intai valoarea la 8 si apoi o printeaza.
La linia urmatoare, evaluarea e la fel de la dreapta la stanga: ultimul argument e preincrementat si il ridica pe "b" la 4, il printeaza, apoi mijlociul e postincrementat, deci intai printeaza 4 si apoi il ridica la 5 dupa care vine si primul argument care, fiind tot postincrementat va printa mai intai valoarea 5 si abia apoi o va incrementa. Dar, atentie, doar evaluarea argumentelor se face de la dreapta la stanga, printarea lor, totusi, se executa bine incepand cu primul.
Dar e posibil ca rezultatul sa fie diferit daca evaluarea argumentelor functiei se face de la stanga la dreapta. Aici se face un abuz de "elasticitate" sau "libertate" oferita de limbajul C, care e foarte generos in aceasta privinta, si nu e recomandat un astfel de mod de programare.

[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]

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.

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.