# bits 'game'

Discussion in 'Mathematics and Physics' started by electroRF, Jan 10, 2014.

Not open for further replies.
1. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
What you can do in C, you can do in assembler. And the concept of promoting variables is exactly the same. And promoting variables is exactly in the heart of the original problem.
What is the minimum number of bits that you need to promote your variables to so that overflow is avoided? That is essentially the question.

If the variables are not allowed to be expanded, then why ask the minimum number of bits needed? That would be just stupid.
Of course the variables are epanded.. that is the whole point of the question. How much you need to expand to avoid overflow?

Last edited: Jan 12, 2014
2. ### RatchitWell-Known Member

Joined:
Mar 12, 2008
Messages:
1,961
Likes:
84
MisterT,

"What you can do in C, you can do in assembler. And the concept of promoting variables is exactly the same. And promoting variables is exactly in the heart of the original problem.
What is the minimum number of bits that you need to promote your variables to so that overflow is avoided? That is essentially the question."

It depends on what you mean by promote. To me it means extending 8-bits to 16-bits, or 16-bits to 32-bits, etc. I cannot extend 8-bits to 12-bits unless the CPU hardware supports a 12 bit word. Sure, I can load a 11-bit+sign bit into a 16-bit word, but the add/sub instruction will not act the same as if the hardware word size was 12 bits.

"If the variables are not allowed to be expanded, then why ask the minimum number of bits needed? That would be just stupid.
Of course the variables are epanded.. that is the whole point of the question. How much you need to expand to avoid overflow?"

This is a theoretical problem for an imaginary CPU, and is not applicable to 8,16,32-bit word size computers.

Ratch

3. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
Like you said, this is a theoretical problem, so extending from 8 bit precision to 10 bits is perfectly valid promotion. Promotion means simply increasing the precision (number of bits) of a variable.
In a real computer where you are allowed to use only 8, 16, 32 bits etc, you would do a "sign extension". http://en.wikipedia.org/wiki/Sign_extension

Joined:
Jan 12, 1997
Messages:
-
Likes:
0

5. ### RatchitWell-Known Member

Joined:
Mar 12, 2008
Messages:
1,961
Likes:
84

Yes, I am very familiar with sign extension. But since the hardware does not support word sizes other than 8,16,32, etc, you cannot use C's handling of oversize values to support regarding 255 as a valid 8 bit signed number.

Ratch

Last edited: Jan 12, 2014
6. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
I tried to compile this code with gnu C on i86 linux:

Code (C):
#include <stdio.h>

unsigned char c(unsigned char i, unsigned char j) {
return i&j;
}

void cl(unsigned u, signed i) {
printf("32-bit comparison: %s\n",(u == i) ? "equal": "different");
}

void dl (unsigned u, signed i) {
long long x = u - i;
printf("32-bit difference: %lld\n",x);
}

void cll(unsigned long long u, signed long long i) {
printf("64-bit comparison: %s\n",(u == i) ? "equal": "different");
}

void dll(unsigned long long u, signed long long i) {
long long x = u - i;
printf("64-bit difference: %lld\n",x);
}

extern int main (int argc, char **argv) {

unsigned u = -1;
long i = 4294967295U;

cl(u,i);
dl(u,i);

cll(u,i);
dll(u,i);

}
And here's what it printed:

Code (text):
32-bit comparison: equal
32-bit difference: 0
64-bit comparison: different
64-bit difference: 4294967296
No evidence of promotion. It does "promote" from shorter types to 32-bit, but only because this is a 32-bit processor and it does all the calculations in 32-bit even if it doesn't need the promotion. For example, the following code from the above program

Code (C):
unsigned char c(unsigned char i, unsigned char j) {
return i&j;
}
"promotes" both operands to 32-bit even if there's absolutely no need:

Code (ASM):
c:
pushl    %ebp
movl    %esp, %ebp
subl    \$8, %esp
movl    8(%ebp), %edx
movl    12(%ebp), %eax
movb    %dl, -4(%ebp)
movb    %al, -8(%ebp)
movb    -8(%ebp), %al
movb    -4(%ebp), %dl
andl    %edx, %eax
leave
ret

7. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
I am using the idea of promoting variables to support it. Not C language. C language is just handy to give real-world examples.
How can you say that 255 becomes -1, if the number is defined to be unsigned 255!!!? Of course if you interpret the same bit-pattern as 2's complement, then it is the decimal number -1. But you'll have to be very careless to make a mistake like that.
Allowing both signed and unsigned numbers to be used is the only way to find the absolute min and max values that the function can possibly have. Of course it is important to keep track what number is signed and what is unsigned.

8. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
Sorry, I messed up with the assignments in the code. But I changed it, re-compiled and still the same result - no promotions.

Code (C):
#include <stdio.h>

unsigned char c(unsigned char i, unsigned char j) {
return i&j;
}

void cl(unsigned u, signed i) {
printf("32-bit comparison: %s\n",(u == i) ? "equal": "different");
}

void dl (unsigned u, signed i) {
long long x = u - i;
printf("32-bit difference: %lld\n",x);
}

void cll(unsigned long long u, signed long long i) {
printf("64-bit comparison: %s\n",(u == i) ? "equal": "different");
}

void dll(unsigned long long u, signed long long i) {
long long x = u - i;
printf("64-bit difference: %lld\n",x);
}

extern int main (int argc, char **argv) {

unsigned u = 4294967295U;
signed i = -1;

cl(u,i);
dl(u,i);

cll(u,i);
dll(u,i);

}

9. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
You need explicit promotions/casting when you compare unsigned with signed. That is a trap that causes lots of bugs.

in this:
int si = -1;
unsigned int ui = 1;
printf("%d\n", si < ui);

Both variables are treated as unsigned (signed is converted to unsigned, in this case MAX value). And the result is opposite that you would expect.

There are more examples and solutions to them in this webpage: https://www.securecoding.cert.org/confluence/display/seccode/INT02-C. Understand integer conversion rules

10. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
That's what I was trying to demonstrate with my code. You cannot rely on the compiler to do the right thing. You need to use correct types and be aware of the binary representation.

BTW: Some languages do extend operands. Delphi would extend both into 64-bit integers for this comparison. I don't think it's a good idea though.

11. ### RatchitWell-Known Member

Joined:
Mar 12, 2008
Messages:
1,961
Likes:
84
As a programmer, you can consider 255 to be anything you want, but the hardware that controls the overflow flag is going to consider 255 to be a negative 8-bit signed number if the word size is 8 bits. If you add any positive number to it, the overflow flag will never trigger.

Ratch

12. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
So, you say that it is impossible to have an unsigned 8-bit number with value 255 in a computer because it is always forced to be signed? Is that really what you are saying?
If the variable is defined as unsigned.. then it is treated as unsigned. And if the variable is treated as unsigned, then it behaves like unsigned.
When that number is used in a calculation, then it is promoted accordingly.

13. ### RatchitWell-Known Member

Joined:
Mar 12, 2008
Messages:
1,961
Likes:
84
No, I am saying the computer hardware that controls the overflow and carry flags operate independently regardless of what you consider the number to be. The hardware will consider 255 to be a negative signed number. If you are saying the number is put into a larger register, then you are going beyond the scope of the problem. The problem simply requires a calculation of the theoretical word size to do those calcuations without triggering a overflow flag. All references to C and discussion of how C handles or promotes oversize values is not pertinent to the problem.

Ratch

Last edited: Jan 12, 2014
14. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
Now you are mixing a real world computer and theoretical questions. Of course computers need to be programmed by somebody. And of course that somebody needs to know if a variable is unsigned or signed and write code that handles the variables correctly. Last time I checked, the value 255 fits perfectly in 8-bit register, and it did not turn to negative number by itself!!

No I'm not! The problem is to find out how big that larger register needs to be!

15. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
Hardware usually has a number of flags which are set as a result of particular instructions. Depending on what flags you use, you can detect either signed or unsigned overflow.

16. ### RatchitWell-Known Member

Joined:
Mar 12, 2008
Messages:
1,961
Likes:
84
MisterT,

"Last time I checked, the value 255 fits perfectly in 8-bit register, and it did not turn to negative number by itself!!"

Numbers are determined by the overflow hardware to be positive or negative by whether the leftmost bit is set or not. Unsigned 255 sets the leftmost bit, so the overflow hardware considers the number to be signed negative. Please don't come back and say the number needs to be considered by the programmer to be negative. If the programmer considers the number to be unsigned, then the overflow flag is ignored.

NorthGuy,

"Hardware usually has a number of flags which are set as a result of particular instructions. Depending on what flags you use, you can detect either signed or unsigned overflow. "

Yes, I know that.

Ratch

17. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
I'm saying that numbers are promoted first. Then added/subtracted or whatever. And when 255 is promoted, then the leftmost bit is not set anymore.

18. ### RatchitWell-Known Member

Joined:
Mar 12, 2008
Messages:
1,961
Likes:
84
You are repeating yourself. That method has been addressed. I aver that the problem does not sanction that operation, and a wrong solution will be obtained. If you repeat that statement, I will not respond to it anymore.

Ratch

19. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
That is where you are wrong.
But, I would like to hear how you think the problem should be approached.

Joined:
Mar 12, 2008
Messages:
1,961
Likes:
84

Ratch

21. ### misterTWell-Known MemberMost Helpful Member

Joined:
Apr 19, 2010
Messages:
2,697
Likes:
368
Location:
Finland
Not a very good academic analysis because you are not using the whole range that 8-bits can represent.