Velocity Reviews > C++ > Boolean operation and arithmetic operation

# Boolean operation and arithmetic operation

Buzz Lightyear
Guest
Posts: n/a

 08-12-2009
Hi, guys,
If I got a expression

int a,b,c,d;

a & (~b + 1) ^ ( ! c * 5 - 10 ) | d;

You see this expression combined with boolean logic and arithmetic
algebra oepration.

How do I simplify this expression and get its value with my pencil,
but not C++ compiler?

It seems very mysterious to me...

Although I checked some Boolean logic reference, but they all focus on
*pure* Boolean logic, but not consider other arithmetic factors, for
example a^(b | c) ^ d = (a ^b^d) | (a^c^d) ...

Thanks!

Pascal J. Bourguignon
Guest
Posts: n/a

 08-12-2009
Buzz Lightyear <(E-Mail Removed)> writes:

> Hi, guys,
> If I got a expression
>
> int a,b,c,d;
>
> a & (~b + 1) ^ ( ! c * 5 - 10 ) | d;
>
> You see this expression combined with boolean logic and arithmetic
> algebra oepration.
>
> How do I simplify this expression and get its value with my pencil,
> but not C++ compiler?
>
> It seems very mysterious to me...

Yes. That's because you are using the wrong word.
&, ^, | and ~ are NOT boolean operators.
They are BITWISE operators.

> a & (~b + 1) ^ ( ! c * 5 - 10 ) | d;

~b negates all the bits of b (it's also called the one-complement).

~b+1 is the two-complement of b. If the target processor uses
two-complement to encode negative numbers, then it corresponds to -b

a&(~b+1) will give an integer with the only be set that are common in
a and (~b+1).

!c is the boolean not; the result is either 0 or 1 depending on
whether c is not 0 or 0.

so !c*5-10 is (c==0)?-5:-10
On a computer using two-complement for negative integers, it's
111...111011 or 111...1110111

So a&(~b+1)^(!c*5-10) will invert all the bits of a&(~b+1) but the
second or third depending on whether c is 0 or non 0.

Finally, a&(~b+1)^(!c*5-10)|d will return an integer with all the bits
that are set in a&(~b+1)^(!c*5-10) or d.

> Although I checked some Boolean logic reference, but they all focus on
> *pure* Boolean logic, but not consider other arithmetic factors, for
> example a^(b | c) ^ d = (a ^b^d) | (a^c^d) ...

You may consider that each int is actually a vector of
CHAR_BIT*sizeof(int) booleans, and that these bitwise operators are
vectorial operations working in parallel on all boolean of these
vectors.

--
__Pascal Bourguignon__

Buzz Lightyear
Guest
Posts: n/a

 08-12-2009
On Aug 12, 5:33*pm, (E-Mail Removed) (Pascal J. Bourguignon)
wrote:
> Buzz Lightyear <(E-Mail Removed)> writes:
> > Hi, guys,
> > If I got a expression

>
> > int a,b,c,d;

>
> > a & (~b + 1) ^ ( ! c * 5 - 10 ) *| d;

>
> > You see this expression combined with boolean logic and arithmetic
> > algebra oepration.

>
> > How do I simplify this expression and get its value with my pencil,
> > but not C++ compiler?

>
> > It seems very mysterious to me...

>
> Yes. * That's because you are using the wrong word.
> &, ^, | and ~ *are NOT boolean operators.
> They are BITWISE operators.
>
> > a & (~b + 1) ^ ( ! c * 5 - 10 ) *| d;

>
> ~b negates all the bits of b (it's also called the one-complement).
>
> ~b+1 is the two-complement of b. *If the target processor uses
> two-complement to encode negative numbers, then it corresponds to -b
>
> a&(~b+1) will give an integer with the only be set that are common in
> a and (~b+1).
>
> !c is the boolean not; the result is either 0 or 1 depending on
> whether c is not 0 or 0.
>
> so !c*5-10 is (c==0)?-5:-10
> On a computer using two-complement for negative integers, it's
> 111...111011 or *111...1110111
>
> So a&(~b+1)^(!c*5-10) will invert all the bits of a&(~b+1) but the
> second or third depending on whether c is 0 or non 0.
>
> Finally, a&(~b+1)^(!c*5-10)|d will return an integer with all the bits
> that are set in a&(~b+1)^(!c*5-10) or d.
>
> > Although I checked some Boolean logic reference, but they all focus on
> > *pure* Boolean logic, but not consider other arithmetic factors, for
> > example *a^(b | c) ^ d *= (a ^b^d) | (a^c^d) ...

>
> You may consider that each int is actually a vector of
> CHAR_BIT*sizeof(int) booleans, and that these bitwise operators are
> vectorial operations working in parallel on all boolean of these
> vectors.
>
> --
> __Pascal Bourguignon__

Thanks! So is there some system reference or theories on these BITWISE
operations, for instance "Associative Laws", "Distributive Laws" or
"Communtative Laws".

Is this true?
a ^ ( b + c) = a ^ b + a ^ c;

Thanks!!!

Tim Love
Guest
Posts: n/a

 08-12-2009
Buzz Lightyear <(E-Mail Removed)> writes:

>> So is there some system reference or theories on these BITWISE

>operations, for instance "Associative Laws", "Distributive Laws" or
>"Communtative Laws".

Try googling for "C++ Operator Precedence and Associativity", etc.

Michael Doubez
Guest
Posts: n/a

 08-12-2009
On 12 août, 11:44, Buzz Lightyear <(E-Mail Removed)> wrote:
> On Aug 12, 5:33*pm, (E-Mail Removed) (Pascal J. Bourguignon)
> wrote:
>
>
>
> > Buzz Lightyear <(E-Mail Removed)> writes:

> > > int a,b,c,d;
> > > a & (~b + 1) ^ ( ! c * 5 - 10 ) *| d;

>
> > > You see this expression combined with boolean logic and arithmetic
> > > algebra oepration.

>
> > > How do I simplify this expression and get its value with my pencil,
> > > but not C++ compiler?

>
> > > It seems very mysterious to me...

>
> > Yes. * That's because you are using the wrong word.
> > &, ^, | and ~ *are NOT boolean operators.
> > They are BITWISE operators.

[snip]
> Thanks! So is there some system reference or theories on these BITWISE
> operations, for instance "Associative Laws", "Distributive Laws" or
> "Communtative Laws".

The same as boolean algebra but for each bit.

>
> Is this true?
> a ^ ( b + c) = a ^ b + a ^ c;

No: a=b=c=1
a ^ ( b + c) = 1 ^ ( 1 + 1 = 1 ^ 2 = 3
a ^ b + a ^ c = 1 ^ 1 + 1 ^ 1 = 0 + 0 = 0

Note: operator + is addition not logical-or

Were you thinking of ?
a ^ ( b | c ) = a ^ b | a ^ c;

--
Michael

Alexander Bartolich
Guest
Posts: n/a

 08-12-2009
Buzz Lightyear wrote:
> [...]
> Thanks! So is there some system reference or theories on these BITWISE
> operations, for instance "Associative Laws", "Distributive Laws" or
> "Communtative Laws".

Sure. These theories are colloquially called "The Standard".

> Is this true?
> a ^ ( b + c) = a ^ b + a ^ c;

This line does not compile. It is not a valid C++ statement.
Perhaps you intented to write »==« instead of »=«.

\$ nl -ba c.c
1 #include <iostream>
2 using namespace std;
3 int main()
4 {
5 int a = 3, b = 4, c = 5;
6 cout << (a ^ ( b + c)) << endl;
7 cout << (a ^ b + a ^ c) << endl;
8 return 0;
9 }

\$ g++ c.c && ./a.out
10
1

So the value of »a ^ ( b + c)« does not equal the value of
»a ^ b + a ^ c«.

--
Brüder, in die Tonne die Freiheit,
Brüder, ein Stoppschild davor.
Egal was die Schwarzen Verlangen
Rufen wir: Ja! Brav im Chor.

Buzz Lightyear
Guest
Posts: n/a

 08-12-2009
On Aug 12, 6:36*pm, Alexander Bartolich <(E-Mail Removed)>
wrote:
> Buzz Lightyear wrote:
> > [...]
> > Thanks! So is there some system reference or theories on these BITWISE
> > operations, for instance "Associative Laws", "Distributive Laws" or
> > "Communtative Laws".

>
> Sure. These theories are colloquially called "The Standard".
>
> > Is this true?
> > a ^ ( b + c) = a ^ b + a ^ c;

>
> This line does not compile. It is not a valid C++ statement.
> Perhaps you intented to write »==« instead of »=«.
>
> \$ nl -ba c.c
> * * *1 *#include <iostream>
> * * *2 *using namespace std;
> * * *3 *int main()
> * * *4 *{
> * * *5 * *int a = 3, b = 4, c = 5;
> * * *6 * *cout << (a ^ ( b + c)) << endl;
> * * *7 * *cout << (a ^ b + a ^ c) << endl;
> * * *8 * *return 0;
> * * *9 *}
>
> \$ g++ c.c && ./a.out
> 10
> 1
>
> So the value of »a ^ ( b + c)« does not equal the value of
> »a ^ b + a ^ c«.
>
> --
> Brüder, in die Tonne die Freiheit,
> Brüder, ein Stoppschild davor.
> Egal was die Schwarzen Verlangen
> Rufen wir: Ja! Brav im Chor.

Thanks, guys.

Yes. I intend to write
Whether: a ^ ( b + c) == a ^ b + a ^ c

I know it might be wrong, but how to prove it.

C++ compiler only could tell me what the result is, but don't tell me
any advanced theory behind the result I think.
It's a prove question I think.

How to prove the following asserts

Whether
a ^ ( b + c) != a ^ b + a ^ c
a v ( b + c) != a v b + a v c;
a ^ (~b) ?= ~ ( a ^ b)
a ^ ( b v c ) == (a ^ b) v (a ^ c)
etc...

a, b ,c: Real numbers.
^: And
v: Or
~: Revert

Pascal J. Bourguignon
Guest
Posts: n/a

 08-12-2009
Buzz Lightyear <(E-Mail Removed)> writes:

> On Aug 12, 6:36*pm, Alexander Bartolich <(E-Mail Removed)>
> wrote:
>> Buzz Lightyear wrote:
>> > [...]
>> > Thanks! So is there some system reference or theories on these BITWISE
>> > operations, for instance "Associative Laws", "Distributive Laws" or
>> > "Communtative Laws".

>>
>> Sure. These theories are colloquially called "The Standard".
>>
>> > Is this true?
>> > a ^ ( b + c) = a ^ b + a ^ c;

>>
>> This line does not compile. It is not a valid C++ statement.
>> Perhaps you intented to write »==« instead of »=«.
>>
>> \$ nl -ba c.c
>> * * *1 *#include <iostream>
>> * * *2 *using namespace std;
>> * * *3 *int main()
>> * * *4 *{
>> * * *5 * *int a = 3, b = 4, c = 5;
>> * * *6 * *cout << (a ^ ( b + c)) << endl;
>> * * *7 * *cout << (a ^ b + a ^ c) << endl;
>> * * *8 * *return 0;
>> * * *9 *}
>>
>> \$ g++ c.c && ./a.out
>> 10
>> 1
>>
>> So the value of »a ^ ( b + c)« does not equal the value of
>> »a ^ b + a ^ c«.
>>
>> --
>> Brüder, in die Tonne die Freiheit,
>> Brüder, ein Stoppschild davor.
>> Egal was die Schwarzen Verlangen
>> Rufen wir: Ja! Brav im Chor.

>
> Thanks, guys.
>
> Yes. I intend to write
> Whether: a ^ ( b + c) == a ^ b + a ^ c
>
> I know it might be wrong, but how to prove it.

The above program execution proves it is wrong.

> C++ compiler only could tell me what the result is, but don't tell me
> any advanced theory behind the result I think.

You don't need any advanced theory to prove something is wrong. You
just need an example of how it is wrong, which is what the above
program does.

> It's a prove question I think.
>
> How to prove the following asserts
>
> Whether
> a ^ ( b + c) != a ^ b + a ^ c

FALSE.

Apart from the example above, in general propositions mixing bitwise
operators and additions will be false more often, because the bits
resulting from an addition may depend on bits of lower order, while
bits resulting of a bitwise operation depend only on bits of the same
order.

> a v ( b + c) != a v b + a v c;

v is not a C or C++ operator

> a ^ (~b) ?= ~ ( a ^ b)

?= is not a C or C++ operator.

> a ^ ( b v c ) == (a ^ b) v (a ^ c)

v is not a C or C++ operator.

> a, b ,c: Real numbers.

There is no Real number in C or C++.

> ^: And

No. As I explained in my previous post, ^ is not AND, it's is a
BITWISE and operation.

> v: Or

No. This is not a C or C++ operator.

> ~: Revert

No. As I explained in my previous post, ~ is nto a "revert" (what
would that be???), it's is a BITWISE not operation.

You should be more careful and focused.

Do not mix mathematics and C or C++. If you have questions about
boolean algebra, you could try news:sci.math

--
__Pascal Bourguignon__

Alexander Bartolich
Guest
Posts: n/a

 08-12-2009
Buzz Lightyear wrote:
> [...]
> Whether
> a ^ ( b + c) != a ^ b + a ^ c
> a v ( b + c) != a v b + a v c;
> a ^ (~b) ?= ~ ( a ^ b)
> a ^ ( b v c ) == (a ^ b) v (a ^ c)
> etc...
>
> a, b ,c: Real numbers.

The bitwise representation of floating point numbers is platform
depended but in any case complex. Have a look at

http://en.wikipedia.org/wiki/IEEE_754-1985

Applying bitwise operations to all bits of a floating point expression
generally makes no sense.

Applying logical operations to a floating point expression involves
exact comparison to 0. Because of the fuzziness of floating point
values you should rather check for a epsilon-neighborhood.

> ^: And
> v: Or
> ~: Revert

The operators of C/C++ have a defined semantic and precedence.

--
Brüder, in die Tonne die Freiheit,
Brüder, ein Stoppschild davor.
Egal was die Schwarzen Verlangen
Rufen wir: Ja! Brav im Chor.

Pascal J. Bourguignon
Guest
Posts: n/a

 08-12-2009
Buzz Lightyear <(E-Mail Removed)> writes:
> Yes. I intend to write
> Whether: a ^ ( b + c) == a ^ b + a ^ c
>
> I know it might be wrong, but how to prove it.

[itex]

http://en.wikipedia.org/wiki/Boolean...ntroduction%29

Proving the basic laws is done like with any other algebraic
structure, buy starting from the definition of the operations.

Then you can prove more complex equivalences either by enumerating all
the cases (2^n, with n being the number of variables), or from the
operations axioms and the laws you proved so far.
[/itex]

--
__Pascal Bourguignon__