Boolean operation and arithmetic operation

B

Buzz Lightyear

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!
 
P

Pascal J. Bourguignon

Buzz Lightyear said:
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.
 
B

Buzz Lightyear

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


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


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.

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!!!
 
T

Tim Love

Buzz Lightyear said:
operations, for instance "Associative Laws", "Distributive Laws" or
"Communtative Laws".

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

Michael Doubez

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;
 
A

Alexander Bartolich

Buzz said:
[...]
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 »=«.
Anyway, why don't you just ask your compiler about it?

$ 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«.
 
B

Buzz Lightyear

Buzz said:
[...]
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 »=«.
Anyway, why don't you just ask your compiler about it?

$ 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
 
P

Pascal J. Bourguignon

Buzz Lightyear said:
Buzz said:
[...]
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 »=«.
Anyway, why don't you just ask your compiler about it?

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


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


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
 
A

Alexander Bartolich

Buzz said:
[...]
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.
Please, don't make up your own notation.
 
P

Pascal J. Bourguignon

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

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

<math>
You might also want to start reading this article:

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.
</math>
 
A

Alexander Bartolich

Pete said:
Alexander said:
[...]
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«.
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top