Skip navigation

Tag Archives: boolean

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.14 (this one was kind of fun!):

Using only bit-level and logical operations, write a C expression that
is equivalent to x == y. In other words, it will return 1 when x and y
are equal and 0 otherwise.


  bit operations:

  | with 1:   | with 0:
  1 | 1 = 1   1 | 0 = 1
  0 | 1 = 1   0 | 0 = 0

  & with 1:   & with 0:
  1 & 1 = 1   1 & 0 = 0
  0 & 1 = 0   1 & 0 = 0

  ^ with 1:   ^ with 0:
  1 ^ 1 = 0   1 ^ 0 = 1
  0 ^ 1 = 1   0 ^ 0 = 0

  !(x ^ y) should work

different:
  x = 1001001010
  y = 0010010111

      1001001010
   ^  0010010111
  --------------
      1011010101
     !1011010101 = 0x00


equal:
  x = 1000010101
  y = 1000010101

      1000010101
  ^   1000010101
  --------------
      0000000000
     !0000000000 = 0x01

Of course those aren’t bytes, too many bits. Just used some random amount of bits while thinking about it.

Advertisements

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.13:

Suppose that x and y have byte values 0x66 and 0x93, respectively. Fill in the
following table indicating the byte values of the different C expressions:

Expression  Value  Expression   Value
-------------------------------------
  x & y              x && y
-------------------------------------
  x | y              x || y
-------------------------------------
 ~x | ~y            !x || !y
-------------------------------------
  x | !y             x && ~y
-------------------------------------


x & y

    0x66
 &  0x93
 -------

   01100110
 & 10010011
 ----------
   00000010

   0x02

x && y = 0x01

x | y

    0x66
 |  0x93
 -------

   01100110
 | 10010011
 ----------
   11110111

   0xF7

x || y = 0x01

~x | ~y

    ~0x66
 |  ~0x93
 --------

   ~01100110
 | ~10010011
 -----------

   10011001
 | 01101100
 ----------
   11111101

   0xFD

!x || !y = 0x00

x & !y

    0x66
 &  0x01
 -------

   01100110
 & 00000001
 ----------
   00000000

   0x00

 x && ~y

      0x66
 &&  ~0x93
 ---------

      0x66
 &&  ~0x93
 ---------

     01100110
 && ~10010011
 ------------


    01100110
 && 01101100
 -----------

      0x66
 &&   0x6C
 ---------
      0x01


Expression  Value  Expression   Value
-------------------------------------
  x & y      0x02    x && y      0x01
-------------------------------------
  x | y      0xF7    x || y      0x01
-------------------------------------
 ~x | ~y     0xFD    !x || !y    0x00
-------------------------------------
  x | !y     0x00     x && ~y    0x01
-------------------------------------

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.12:

`bis` is a bit set operation and `bic` is a bit clear operation. Both
instructions take a data word x and a mask word m. They generate a
result y consisting of the bits of x modified according to the
bits of m. With `bis`, the modification involves setting z to 1 at
each bit position where m is 1. With `bic`, the modification
involves setting z to 0 at each bit position where m is 1.

Fill in the missing expressions in the following code:


/* Bit Set */
int bis ( int x, int m ) {
  /* Write an expression in C that computes the effect of bit set */
  int result = ______________;
  return result;
}


/* Bit Clear */
int bic ( int x, int m ) {
  /* Write an expression in C that computes the effect of bit clear */
  int result = ______________;
  return result;
}

Boolean logic operations rundown:

  & with 1:    & with 0:
  1 & 1 = 1;   1 & 0 = 0;
  0 & 1 = 0;   0 & 0 = 0;

  | with 1:    | with 0:
  1 | 1 = 1    1 | 0 = 1
  1 | 0 = 1    0 | 0 = 0

  ^ with 1:    ^ with 0:
  1 ^ 1 = 0    1 ^ 0 = 1
  0 ^ 1 = 1    0 ^ 0 = 0

Solution:

for bis (sets result to 1 for all 1's in m):

  int result = x | m;

for bic (sets result to 0 for all 1's in m):

  int result = x & ~m;


This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.11:

Write C expressions for the following values, with the result for x = 0x98FDECBA
and a w 32-bit word size shown in square brackets:

A. The least signficant byte of x, with all other bits set to 1 [0xFFFFFFBA].
B. The complement of the least signficant byte of x, with all other bytes left
   unchanged [0x98FDEC45].
C. All but the least signficant byte of x, with the least signficant byte set to
   0 [0x98FDEC00].

Although our examples assume a 32-bit word size, your code should work for
any word size w >= 8.


A.
      0x98FDECBA
          ?
    ------------
      0xFFFFFFBA

      0x98FDECBA
    |      ~0xFF
    ------------
      0xFFFFFFBA

    x | ~0xFF = 0xFFFFFFBA

B.

      0x98FDECBA
          ?
    ------------
      0x98FDEC45

      complement:
      0^1 = 1
      1^1 = 0

      unchanged:
      1^0 = 1
      0^0 = 0

      0x98FDECBA
    ^       0xFF
    ------------
      0x98FDEC45

    x ^ 0xFF = 0x98FDEC45

C.

      0x98FDECBA
          ?
    ------------
      0x98FDEC00

      possible operations:

      | with 0:
      1|0 = 1 <-- want 0's so this doesn't work

      | with 1;
      1|1 = 1 <-- nope
      0|1 = 1 <-- nope

      & with 1:
      1&1 = 1 <-- no
      0&1 = 0
      & with 1 leaves existing values in place

      & with 0:
      1&0 = 0
      0&0 = 0
      ^^^ that's it, no matter what input, & with 0 will flip bits to 0

      ^ with 1:
      1^1 = 0
      0^1 = 1 <-- no

      ^ with 0:
      1^0 = 1 <-- no
      0^0 = 0

      0x98FDECBA
    &      ~0xFF
    ------------
      0x98FDEC00


  x & ~0xFF = 0x98FDEC00

This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.10:

To show how the ring properties of ^ can be useful, consider the following
program:
void implace_swap( int *x, int *y ) {
  *x = *x ^ *y; /* Step 1 */
  *y = *x ^ *y; /* Step 2 */
  *x = *x ^ *y; /* Step 3 */
}
Starting with values a and b in the locations pointed to by x and y,
respectively, fill in the table that follows giving the values stored
at the two locations after each step of the procedure. Use the ring
properties to show that the desired effect is achieved. Recall that
every element is its own additive inverse (that is, a ^ a = 0).


Step           *x                  *y
------------------------------------------------
Initially       a                   b
------------------------------------------------
Step 1         a^b                  b
------------------------------------------------
Step 2         a^b            (a^b)^b=(b^b)^a=a
------------------------------------------------
Step 3    (a^b)^a=(a^a)^b=b         a
------------------------------------------------


This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.9:

We can create eight different colors based on the absence (0) or presence
(1) of light sources R, G, and B:

  R  G  B  Color
 ------------------
  0  0  0  Black
 ------------------
  0  0  1  Blue
 ------------------
  0  1  0  Green
 ------------------
  0  1  1  Cyan
 ------------------
  1  0  0  Red
 ------------------
  1  0  1  Magenta
 ------------------
  1  1  0  Yellow
 ------------------
  1  1  1  White
 ------------------

This set of colors forms an eight-element Boolean algebra.

A. The complement of a color is formed by turning off the lights that are on
and turning on the lights that are off. What would be the complements of
the eight colors listed above?

B. What colors correspond to Boolean values 0^w and 1^w for this algebra?

C Describe the effect of applying Boolean operations on the following colors:

      Blue | Red   =
   Magenta & Cyan  =
     Green ^ White =

A.

  R  G  B  Color       R  G  B  Complement
 -----------------------------------------
  0  0  0  Black    =  1  1  1   White
 ------------------------------------------
  0  0  1  Blue     =  1  1  0   Yellow
 ------------------------------------------
  0  1  0  Green    =  1  0  1   Magenta
 ------------------------------------------
  0  1  1  Cyan     =  1  0  0   Red
 ------------------------------------------
  1  0  0  Red      =  0  1  1   Cyan
 ------------------------------------------
  1  0  1  Magenta  =  0  1  0   Green
 ------------------------------------------
  1  1  0  Yellow   =  0  0  1   Blue
 ------------------------------------------
  1  1  1  White    =  0  0  0   Black
 ------------------------------------------


B.

  0^w is Black
  1^w is White

C.

  Blue  |  Red =   0 0 1
                   1 0 0
                   -----
                   1 0 1  = Magenta

  Magenta & Cyan = 1 0 1
                   0 1 1
                   -----
                   0 0 1  = Blue

  Green ^ White  = 0 1 0
                   1 1 1
                   -----
                   1 0 1  = Magenta


This solution is for the book I am currently reading. All of my notes and solutions are available at Google Code.

Here is my work for problem 2.8:

Fill in the following table showing the results of evaluating Boolean operations
on bit vectors.


------------------------------
| Operation |     Result     |
------------------------------
|    a      |   [01101001]   |
|    b      |   [01010101]   |
------------------------------
|   ~a      |   [10010110]   |
|   ~b      |   [10101010]   |
------------------------------
|  a & b    |   [01000001]   |
|  a | b    |   [01111101]   |
|  a ^ b    |   [00111100]   |
------------------------------