R0b0t1
2009-02-14 20:45:58
In applications where memory is important, booleans are usually held in multiples in something like an integer. The reason being is that the Boolean type – unless the language provides explicit optimizations for it – is really just an Integer. This can be seen in C++'s std::vector, where std::vector<bool> uses an array of integers, but stores individual booleans as bits in the integer.
So, in a single integer, I can store 32 booleans.
In languages like C, some people try to fit multiple values into an integer and, as such, use a series of flags. However, for booleans, you need simply one bit set and can simply use a left shift on 1.
Now, the important part is the (bits and (1 shl 15)). Now, as you should know, "and" will only return true if both of its operands are true. So, should the 15th bit of bits be true, your boolean value would, then, be true.
So, you might have noticed this looks a bit like an array. Well, it is, technically, an array of bits.
Now, the other technique I talked about was storing multiple values (usually integers, but integers that require a small memory space) inside of a larger integer. It would be useful if you understand how hexadecimal numbering in relation to binary values works…
So, from this excerpt from my sudoku solver, you should be able to see that the first eight bits/first byte will be used to store the index position. To retrieve this value it is but a simple matter of (Integer and $FF), as each character is four bits, and F stands for 15, so F is 1111. You'd set them by simply saying (Integer := Integer and N), where N is less than 255, the largest number a byte can support.
The next four after that, however, are a bit (no pun intended) harder to access. You would get them with (Integer and ($F shl 8)) or (Integer and $F00), as the four bits are 8 spaces over from the start. To set it, use (Integer := Integer and (N shl 8)), where N must be less than 15 in this case.
So, as the next usable block is 16 bits over, we know we will need to shl by 16. And we know that we are using a full byte… and one more bit. That'd simply be (Integer and ($1FF shl 16)) or (Integer and ($1FF0000)).
The last two are very easy. Its (Integer and (1 shl ??). See if you can get it yourself :).
Now, for the sake of learning, let us say that we want to clear the Integer we are using of any random junk that may be in it (this really isn't important in Delphi, but in C, you usually end up with a non-initialized slot). Let's make up a bitmask for it.
So, we know the first mask, $FF, and the second, $F00. So we'd have $FFF. The next four aren't used, giving us $0FFF. The next nine after that are used, however, giving us $1FF0FFF. So far, pretty easy. But now you'd be good to notice we skip the next five and use the last two. This is where good counting comes in ;)
If we know that 1100 is 12, which is C, then we should have $C1FF0FFF in the end.
So, in a single integer, I can store 32 booleans.
0000-0000 0000-0000 0000-0000 0000-0000
In languages like C, some people try to fit multiple values into an integer and, as such, use a series of flags. However, for booleans, you need simply one bit set and can simply use a left shift on 1.
program Example;
function IntToBool(I: Integer): Boolean;
begin
Result := I <> 0;
end;
var
bits: Integer;
BitIsTrue: Boolean;
begin
{ 0000-0000 0000-0000 0000-0000 0000-0000 }
bits := 1 shl 15;
{ should now be:
0000-0000 0000-0000 1000-0000 0000-0000 }
BitIsTrue := IntToBool(bits and (1 shl 15));
WriteLn(BoolToStr(BitIsTrue));
end.
Now, the important part is the (bits and (1 shl 15)). Now, as you should know, "and" will only return true if both of its operands are true. So, should the 15th bit of bits be true, your boolean value would, then, be true.
So, you might have noticed this looks a bit like an array. Well, it is, technically, an array of bits.
Now, the other technique I talked about was storing multiple values (usually integers, but integers that require a small memory space) inside of a larger integer. It would be useful if you understand how hexadecimal numbering in relation to binary values works…
/* Organization of 32-bit word:
*
* bits 0 - 7 index (0 - 81)
* 8 - 11 value (1 - 9, 0 if not solved)
* 12 - 15 unused
* 16 - 24 possibilties (high if possible)
* 25 - 29 unused
* 30 invalid/error (error somewhere...)
* 31 "stickiness" (set by user)
*
* ___ "stickyness"
* |
* 1100-0001 1111-1111 0000-1111 1111-1111
* | |_________| | |____|
* | | | |
* | possibilities value index
* |
* |____> invalid/error
*/
So, from this excerpt from my sudoku solver, you should be able to see that the first eight bits/first byte will be used to store the index position. To retrieve this value it is but a simple matter of (Integer and $FF), as each character is four bits, and F stands for 15, so F is 1111. You'd set them by simply saying (Integer := Integer and N), where N is less than 255, the largest number a byte can support.
The next four after that, however, are a bit (no pun intended) harder to access. You would get them with (Integer and ($F shl 8)) or (Integer and $F00), as the four bits are 8 spaces over from the start. To set it, use (Integer := Integer and (N shl 8)), where N must be less than 15 in this case.
So, as the next usable block is 16 bits over, we know we will need to shl by 16. And we know that we are using a full byte… and one more bit. That'd simply be (Integer and ($1FF shl 16)) or (Integer and ($1FF0000)).
The last two are very easy. Its (Integer and (1 shl ??). See if you can get it yourself :).
Now, for the sake of learning, let us say that we want to clear the Integer we are using of any random junk that may be in it (this really isn't important in Delphi, but in C, you usually end up with a non-initialized slot). Let's make up a bitmask for it.
So, we know the first mask, $FF, and the second, $F00. So we'd have $FFF. The next four aren't used, giving us $0FFF. The next nine after that are used, however, giving us $1FF0FFF. So far, pretty easy. But now you'd be good to notice we skip the next five and use the last two. This is where good counting comes in ;)
If we know that 1100 is 12, which is C, then we should have $C1FF0FFF in the end.