1. Welcome to our site! Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.
    Dismiss Notice

bits 'game'

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

Thread Status:
Not open for further replies.
  1. misterT

    misterT Well-Known Member Most Helpful Member

    Joined:
    Apr 19, 2010
    Messages:
    2,697
    Likes:
    368
    Location:
    Finland
    ONLINE
    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. Ratchit

    Ratchit Well-Known Member

    Joined:
    Mar 12, 2008
    Messages:
    1,934
    Likes:
    78
    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. misterT

    misterT Well-Known Member Most Helpful Member

    Joined:
    Apr 19, 2010
    Messages:
    2,697
    Likes:
    368
    Location:
    Finland
    ONLINE
    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
     
  4. dave

    Dave New Member

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


     
  5. Ratchit

    Ratchit Well-Known Member

    Joined:
    Mar 12, 2008
    Messages:
    1,934
    Likes:
    78

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

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    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. misterT

    misterT Well-Known Member Most Helpful Member

    Joined:
    Apr 19, 2010
    Messages:
    2,697
    Likes:
    368
    Location:
    Finland
    ONLINE
    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. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    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. misterT

    misterT Well-Known Member Most Helpful Member

    Joined:
    Apr 19, 2010
    Messages:
    2,697
    Likes:
    368
    Location:
    Finland
    ONLINE
    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. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    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. Ratchit

    Ratchit Well-Known Member

    Joined:
    Mar 12, 2008
    Messages:
    1,934
    Likes:
    78
    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. misterT

    misterT Well-Known Member Most Helpful Member

    Joined:
    Apr 19, 2010
    Messages:
    2,697
    Likes:
    368
    Location:
    Finland
    ONLINE
    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. Ratchit

    Ratchit Well-Known Member

    Joined:
    Mar 12, 2008
    Messages:
    1,934
    Likes:
    78
    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. misterT

    misterT Well-Known Member Most Helpful Member

    Joined:
    Apr 19, 2010
    Messages:
    2,697
    Likes:
    368
    Location:
    Finland
    ONLINE
    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. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    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. Ratchit

    Ratchit Well-Known Member

    Joined:
    Mar 12, 2008
    Messages:
    1,934
    Likes:
    78
    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. misterT

    misterT Well-Known Member Most Helpful Member

    Joined:
    Apr 19, 2010
    Messages:
    2,697
    Likes:
    368
    Location:
    Finland
    ONLINE
    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. Ratchit

    Ratchit Well-Known Member

    Joined:
    Mar 12, 2008
    Messages:
    1,934
    Likes:
    78
    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. misterT

    misterT Well-Known Member Most Helpful Member

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

    Ratchit Well-Known Member

    Joined:
    Mar 12, 2008
    Messages:
    1,934
    Likes:
    78
    Didn't you read post #8?

    Ratch
     
  21. misterT

    misterT Well-Known Member Most Helpful Member

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

Share This Page