357mag

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:


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:


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?

DaWei

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.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

lectricpharaoh

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:




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



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




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

__________________
A man's knowledge is like an expanding sphere, the surface corresponding to the boundary between the known and the unknown. As the sphere grows, so does its surface; the more a man learns, the more he realizes how much he does not know. Hence, the most ignorant man thinks he knows it all. - L. Sprague de Camp

357mag

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.

357mag

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.

lectricpharaoh

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

__________________
A man's knowledge is like an expanding sphere, the surface corresponding to the boundary between the known and the unknown. As the sphere grows, so does its surface; the more a man learns, the more he realizes how much he does not know. Hence, the most ignorant man thinks he knows it all. - L. Sprague de Camp

357mag

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.

357mag

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


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:


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

lectricpharaoh

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: For Java, it might look like this: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".
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.
Yup. Note that in C/C++, this could have been written like so: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.

__________________
A man's knowledge is like an expanding sphere, the surface corresponding to the boundary between the known and the unknown. As the sphere grows, so does its surface; the more a man learns, the more he realizes how much he does not know. Hence, the most ignorant man thinks he knows it all. - L. Sprague de Camp

357mag

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


Likewise the second time through the loop it does this:


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.