bits 'game'

Status
Not open for further replies.

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.

Ratchit said:
Perhaps the compiler expands the 8-bit word to a larger size if if the value does not fit into 8-bits. If it does, that goes beyond the problem we are discussing.
Click to expand...

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

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:
I tried to compile this code with gnu C on i86 linux:

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

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: 
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
 
Ratchit said:
you cannot use C's handling of oversize values to support regarding 255 as a valid signed number.
Click to expand...

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.
 
Sorry, I messed up with the assignments in the code. But I changed it, re-compiled and still the same result - no promotions.

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);
 
}
 

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: **broken link removed**
 

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.
 

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
 
Ratchit said:
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.
Click to expand...
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.
 

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:
Ratchit said:
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.
Click to expand...
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!!

Ratchit said:
If you are saying the number is put into a larger register, then you are going beyond the scope of the problem.
Click to expand...
No I'm not! The problem is to find out how big that larger register needs to be!
 
Ratchit said:
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.
Click to expand...

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.
 
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
 
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.
 
misterT said:
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.
Click to expand...

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
 
Ratchit said:
I aver that the problem does not sanction that operation, and a wrong solution will be obtained.
Click to expand...
That is where you are wrong.
But, I would like to hear how you think the problem should be approached.
 
Status
Not open for further replies.

Similar threads

Adding HEX bits in a byte.
2
Replies
35
Views
10K
camerart
MIT enters the game? Overunity after all?
Replies
16
Views
3K
Tony Stewart
Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…