bits 'game'

[misterT]

I program in assembler, not C, therefore that link does not mean anything to me. However, the C compiler uses the native word size which is usually larger than 8-bits. I still stand by what I said about 255 being a negative number in signed 8-bit words.

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.

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.

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?

 

[Ratchit]

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

 

[misterT]

It depends on what you mean by promote.

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". https://en.wikipedia.org/wiki/Sign_extension

 

[Ratchit]

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". https://en.wikipedia.org/wiki/Sign_extension

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

 

[NorthGuy]

I tried to compile this code with gnu C on i86 linux:

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

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

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:

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

 

[misterT]

you cannot use C's handling of oversize values to support regarding 255 as a valid signed number.

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.

 

[NorthGuy]

Sorry, I messed up with the assignments in the code. But I changed it, re-compiled and still the same result - no promotions.

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

 

[misterT]

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

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

 

[NorthGuy]

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.

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.

 

[Ratchit]

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.

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

 

[misterT]

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.

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.

 

[Ratchit]

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

 

[misterT]

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.

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

If you are saying the number is put into a larger register, then you are going beyond the scope of the problem.

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

 

[NorthGuy]

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.

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.

 

[Ratchit]

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

 

[misterT]

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.

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.

 

[Ratchit]

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.

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

 

[misterT]

I aver that the problem does not sanction that operation, and a wrong solution will be obtained.

That is where you are wrong.
But, I would like to hear how you think the problem should be approached.

 

[Ratchit]

That is where you are wrong.
But, I would like to hear how you think the problem should be approached.

Didn't you read post #8?

Ratch

 

[misterT]

Didn't you read post #8?

Not a very good academic analysis because you are not using the whole range that 8-bits can represent.