# Boolean operation and arithmetic operation

Discussion in 'C++' started by Buzz Lightyear, Aug 12, 2009.

1. ### Buzz LightyearGuest

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!

Buzz Lightyear, Aug 12, 2009

2. ### Pascal J. BourguignonGuest

Buzz Lightyear <> 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__

Pascal J. Bourguignon, Aug 12, 2009

3. ### Buzz LightyearGuest

On Aug 12, 5:33 pm, (Pascal J. Bourguignon)
wrote:
> Buzz Lightyear <> 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!!!

Buzz Lightyear, Aug 12, 2009
4. ### Tim LoveGuest

Buzz Lightyear <> 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.

Tim Love, Aug 12, 2009
5. ### Michael DoubezGuest

On 12 août, 11:44, Buzz Lightyear <> wrote:
> On Aug 12, 5:33 pm, (Pascal J. Bourguignon)
> wrote:
>
>
>
> > Buzz Lightyear <> 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

Michael Doubez, Aug 12, 2009
6. ### Alexander BartolichGuest

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.

Alexander Bartolich, Aug 12, 2009
7. ### Buzz LightyearGuest

On Aug 12, 6:36 pm, Alexander Bartolich <>
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

Buzz Lightyear, Aug 12, 2009
8. ### Pascal J. BourguignonGuest

Buzz Lightyear <> writes:

> On Aug 12, 6:36 pm, Alexander Bartolich <>
> 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__

Pascal J. Bourguignon, Aug 12, 2009
9. ### Alexander BartolichGuest

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.

Alexander Bartolich, Aug 12, 2009
10. ### Pascal J. BourguignonGuest

Buzz Lightyear <> 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_algebra_(introduction)

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__

Pascal J. Bourguignon, Aug 12, 2009
11. ### Alexander BartolichGuest

Pete Becker wrote:
> Alexander Bartolich wrote:
>> [...]
>> Applying bitwise operations to all bits of a floating point expression
>> generally makes no sense.

>
> Umm, that's exactly how many operations that fiddle with floating-point
> values are implemented. Granted, it's not for beginners. But it often
> does make sense.

The binary representation of an IEEE floating point number comprises
sign, exponent, and fraction. Meaningful manipulation of these parts
involves masking them out with »&«, right shift, doing some integer
math, left shift, and pasting them in again with »|«. This is completely
different from expressions like »3.141 & 2.718«.

>> 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.

>
> Sigh. This is, as always, dead wrong. Floating-point values are not
> fuzzy, they are exact.

http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.17

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

Alexander Bartolich, Aug 12, 2009