Boolean operation and arithmetic operation

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

  1. 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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. 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
    #3
  4. Buzz Lightyear

    Tim Love Guest

    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
    #4
  5. 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
    #5
  6. 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 »=«.
    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.
    Alexander Bartolich, Aug 12, 2009
    #6
  7. 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 »=«.
    > 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
    Buzz Lightyear, Aug 12, 2009
    #7
  8. 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 »=«.
    >> 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++.


    > ^: 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
    #8
  9. 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.
    Please, don't make up your own notation.

    --
    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
    #9
  10. 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.


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

    --
    __Pascal Bourguignon__
    Pascal J. Bourguignon, Aug 12, 2009
    #10
  11. 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
    #11
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Trent Buck

    variadic arithmetic, boolean operators

    Trent Buck, Jan 1, 2005, in forum: C Programming
    Replies:
    3
    Views:
    406
    Mysidia
    Jan 2, 2005
  2. joshc
    Replies:
    5
    Views:
    553
    Keith Thompson
    Mar 31, 2005
  3. J Leonard
    Replies:
    4
    Views:
    12,670
    Mark Space
    Jan 19, 2008
  4. Metre Meter
    Replies:
    7
    Views:
    366
    Metre Meter
    Aug 6, 2010
  5. John Ladasky

    Arithmetic with Boolean values

    John Ladasky, Aug 11, 2012, in forum: Python
    Replies:
    15
    Views:
    324
    Hans Mulder
    Aug 14, 2012
Loading...

Share This Page