Programming Forums - Question about using a mask

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Java (http://www.programmingforums.org/forum17.html)

- - Question about using a mask (http://www.programmingforums.org/showthread.php?t=13639)

Question about using a mask

I'm working with one of Herb Schildt's programs that uses a mask to print an integer's binary equivalent. I've never used a mask before and I think I understand how it's working, but I want to make sure. Let's say I want to print the binary equivalent of the integer 123(0111 1011). Let's say my mask is defined as 1000 0000(which I guess would be 128).

Now the first time through I AND the bits in the leftmost column:

0

1

That will print a 0. Then my right shift operator which is defined in my loop header(mask >>>= 1)will shift the 1 in my mask over to the right by one column, so now my mask looks like 0100 0000. Then the process repeats and now I AND the bits in the second column from the left:

1

1

That will print a 1. Then my right shift operator shifts the 1 in my mask over to the right by one place and the whole business repeats.

My question is how does the compiler know only to work with one column at a time? The compiler only works with the column that has the 1 bit in my mask. Is this why it's called a mask? Because all the other columns in my mask have zero's in them, it basically makes the compiler blind to all those other columns, so in effect the compiler only see's the particular column that is currently holding the 1 bit in my mask?

357, you're going to have to delve into boolean logic. Software drives hardware. Hardware may drive as many simultaneous operations as it is configured to handle.

It is a mystery to me that so many people think that software stands alone. It does not. If it did, one would not need compilers and machines.

I am an old fart, but that part of the equation has not changed, yet.

The compiler translates your code to values that typically can be represented by values stored in a register. The cpu can deal with those binary values in parallell, if it wishes. This is something that your program can do only in roundabout ways.

It can deal with individual bits. It can choose whether to propagate the carry of individual bit operations, or not. You, as the master, need to say.

There are tons of problem solutions that can be written without knowing how the processor works. That's why abstraction was invented and propagated. It's extremely valuable.

On the other hand, if you want to look under the hood, get some coveralls on and buy some Goop to get the grease out. Incidentally, don't expect the expertise to come about because you're a whiz at abstracted solutions. It doesn't work that way, and it won't for some unprescribed number of years to come. Learn facts. Get real. Change facts you don't like. Good luck with the last part, but it happens.

It's all about boolean operations. There are three binary (in the sense of two operands, not in the number base sense) such operations: AND, OR, and XOR. Each uses two boolean (true or false) values, and evaluates to either true or false.

AND is what you were using. It evaluates to true if both the operands are true. Otherwise, it evaluates to false:

http://members.shaw.ca/r.sheppard/temp/booleanAND.png

OR evaluates to true if either operand is true (or if both are true). If both are false, it evaluates to false:

http://members.shaw.ca/r.sheppard/temp/booleanOR.png

XOR evaluates to true if the operands are different. If they are both true or both false, it evaluates to false:

http://members.shaw.ca/r.sheppard/temp/booleanXOR.png

With computers, it should be apparent that you only need a single bit to store a true or false value. A value of one represents true, and a value of zero represents false. Likewise, since you are accessing a byte or larger unit at a time, you can do a bunch of these boolean operations at once. For example, say you have this:

01010101  // operand A

00001111  // operand B

--------

00000101  // result

See how the result in the corresponding bit of the result is the boolean AND of the respective bits in each operand?

This is a common use of AND. It is often used to turn off bits in a value. You set the mask (operand B) bits to one for bits you want to preserve, and to zero for bits you want to turn off. You apply the mask to your source (operand A), and it will turn off the bits whose mask value is zero, and for other bits, it will leave them alone.

For OR, the use is different. It is used to turn on bits in a value. By setting the mask bits to one for certain bits and applying it to the source, it will set those respective bits in the source to one.

XOR is similar, except it is used to toggle bits. By setting a bit in the mask to one, if the respective source bit is also one, the result bit will be zero (both operands the same means the result is false). If the source bit is zero, the result is one (they are different). If the mask bit is zero, it will preserve the original values, rather than toggling them (because source bits of one will XOR with the zero, thus the result is one, or if they are both zero, the result will be zero).

As to how this applies to your original problem, look at it like this. You have a binary value, and you want to print it in binary format. In other words, you want to print "1" for each one bit, and "0" for each zero bit. The easiest approach might be something like this:

public static String intToBinaryString(int value)

{

  String result = "";

  for(int x=31; x>=0; --x)

    result += (((value >> x) & 1) == 1) ? "1" : "0";

  return result;

}

I use the ternary operator here. Basically, it is a compact if-else construct. When you have an expression of the form A ? B : C, the result is B if A is true, and C if A is false. I use the bitwise shift operator to shift value into position (so that the bit I want to test is in position 0, or the far right position). I then AND it with 1, which will evaluate to 1 if the bit was originally 1, and do the test. I then add "1" to result if the comparison was true, or add "0" otherwise. By looping, I first align bit 31 (the leftmost bit) for testing, then bit 30, then bit 29, and so on.

Hopefully, this makes it a little more clear.

[edit] If half the stuff I've heard about Schildt is true, I'd recommend finding other material to learn from. The consensus seems to be that his accuracy leaves much to be desired. [/edit]

I'd rather stick with my(or Herb's example). I think it's easier to follow. I do like his books cuz he provides lots of cool little programs to work with. But his coding style is really bad as far as his use of whitespace.

Getting back to my original question. How does the compiler know to only work with one column at a time? I can clearly see that is what the compiler is doing here. If you have an integer like 123(0111 1011), and your mask is set to 128(1000 0000) when you AND 0 and 1 you print 0. Then you move over to the right one column and you AND 1 and 1 and you print 1. Then you move over to the right one column and you AND 1 and 1 and you print 1.

You work with one column at a time. I know how the boolean AND works. You only get a 1 if both bits are set to 1. But does the fact that my mask is only has a 1 in just one bit position at at time, and 0's in all the other bit positions, does this make the compiler not see all those other columns? I am working with an 8 bit integer, so I have 8 columns.

I've taken some paper and pencil to your example and I can see how that too will do the job. I have an example in my Deitel book where they are doing it yet another way. They mention the word "mask" and "when variable value and MASK are combined using the & operator(AND), all the bits except the high order bit are masked off(hidden), because any bit ANDed with 0 gives 0".

To me it looks like the bottom line no matter what method you chose to write this program is that the compiler will not see those other columns where the zero's are in the mask value. It will only work with the column where the 1 is in the mask value.

Quote:

Originally Posted by 357mag

You work with one column at a time. I know how the boolean AND works. You only get a 1 if both bits are set to 1. But does the fact that my mask is only has a 1 in just one bit position at at time, and 0's in all the other bit positions, does this make the compiler not see all those other columns? I am working with an 8 bit integer, so I have 8 columns.

It 'sees' all the columns. It's just that the result of an AND operation between two bits where one is zero is, well, zero. Let me give you an analogy:

  501

+ 002

-----

  503

In this decimal addition, how do you 'know' to only use one column? The answer is, you don't. You do the addition in each column; it's just that the rightmost one is the only one to have a nonzero value in the second operand. The zeroes in the second operand leave the respective columns unchanged, and as such, it seems they are ignored- but they are not.

Well, I don't know. Back to my(Herb's example). You're saying the first time through the loop we have this going on:

0111 1011
1000 0000
----------
0000 0000 // but the compiler is not printing 0000 0000, it just prints 0

Then the second time through the loop we have:

0111 1011
0100 0000
----------
0100 0000 // but the compiler isn't printing 0100 0000 it just prints 1

And so on. But the compiler only prints in the end 0111 1011. It doesn't print
0000 0000 0100 0000 0010 0000. That what is a little confusing to me. That's why I say it's only looking at the column that has the 1 bit in the mask. Those other columns kind of get masked off(hidden) or ignored. The compiler does not print what is the result of those other columns. It only prints what is the result of the specific column that contains the 1 bit in the mask.

And I do have another question. Another way to write the for header would be to do something like this:

for (; mask != 0; mask >>>= 1)

I have 3 questions about the way this header is working:

1. There is no initialization in the for loop header. Is this because in this particular program, it's simply not needed? This is my guess anyway.

2. The mask != 0 part. This must mean that when the 1 in the mask finally gets shifted out(it falls off the right end) then the mask in effect has the value of zero. In this case this would cause the loop to end. Again, this is my best guess.

3. The mask >>>= 1 part. Here we are using the unsigned right shift instead of the regular >> right shift operator. My understanding is that when you use the unsigned right shift operator it will not preserve the sign bit, so it will bring in a 0 on the left. If I instead used the right shift operator this would cause the compiler to bring in a 1 on the left so my mask would look like this:

1100 0000

It would look like that after the first shift. And that would screw up the program then? Again, that's my guess.

Quote:

Originally Posted by 357mag

Okay, I assumed this was Java. With Java, conditionals must evaluate to true or false; you cannot directly test an int value without the comparison operator. For example, in C++ you get:

int mask = 128;   // 10000000 binary

int value = 123;  // 01111011 binary

for(int x=0; x<32; ++x)

{

  if(value & (mask >> x))  // in C/C++, nonzero result is treated as true

    std::cout << "1";

  else

    std::cout << "0";

 }

For Java, it might look like this:

int mask = 128;   // 10000000 binary

 int value = 123;  // 01111011 binary

 for(int x=0; x<32; ++x)

 {

   if(value & (mask >> x) != 0)  // in Java, result must be boolean

     System.out.print("1");

   else

     System.out.print("0");

  }

In both cases, you see it's not printing out 01000000 binary as "1". Rather, it's testing if 01000000 is nonzero, and if so, it prints out "1". Likewise, if the AND of mask and value equals 00000000 (or just 0), it prints "0".

Quote:

Originally Posted by 357mag

And I do have another question. Another way to write the for header would be to do something like this:

for (; mask != 0; mask >>>= 1)

Yes. Often, though, if the values used in the test condition of the loop are already initialized, you see while() or do..while() loops used instead.

Quote:

Originally Posted by 357mag

2. The mask != 0 part. This must mean that when the 1 in the mask finally gets shifted out(it falls off the right end) then the mask in effect has the value of zero. In this case this would cause the loop to end. Again, this is my best guess.

Yup. Note that in C/C++, this could have been written like so:

while(mask >>= 1)  // assumes mask is unsigned

  // loop body

Quote:

Originally Posted by 357mag

3. The mask >>>= 1 part. Here we are using the unsigned right shift instead of the regular >> right shift operator. My understanding is that when you use the unsigned right shift operator it will not preserve the sign bit, so it will bring in a 0 on the left. If I instead used the right shift operator this would cause the compiler to bring in a 1 on the left

Yes. Although (minor nit) it's not just shift; it's shift and assign. It's much the same as a += b is shorthand for a = a + b. The reason you need an unsigned shift operator is because for whatever reason, the language designers of Java decided not to provide unsigned types.

So let me get this straight. The first time through the loop the compiler is doing this:

0111 1011

1000 0000

----------

0000 0000    // Java interprets the whole thing as false since there is no 1's 

                  // present in any of the bit positions

Likewise the second time through the loop it does this:

0111 1011

0100 0000

----------

0100 0000    // Java interprets this as being true because there is a 1 bit

                  // present

So the compiler looks and does the math for all 8 columns, and if the end result shows a 1 in any of the bit positions, the if statement is true causing the compiler to print a 1.

So the compiler really does see and do the math for all the bit positions, not just one column at a time.