range of an int
in [Learn C or C++]
|
From: Jim Langston on 13 Jan 2008 00:18 conrad wrote: > On Jan 12, 12:18 pm, "Andrew Koenig" <a...(a)acm.org> wrote: >> "conrad" <con...(a)lawyer.com> wrote in message >> >> news:1f2c2da7-e21b-4273-b154-77b4df2549db(a)m34g2000hsf.googlegroups.com... >> >>> What is the purpose behind having ranges >>> for various signed integer types as >>> -2^n and (2^n) - 1? I don't follow >>> why the postive end subtracts 1 >>> from the 2^n value to establish >>> the upper limit. Can someone >>> explain the reasoning behind this? >> >> Let's look at n=4 as an example. >> >> There are 2^n possible distinct values that an n-bit quantity can >> have. If one of those values is zero, and distinct bit patterns >> yield distinct values, then the number of positive values plus the >> number of negative values must be equal to (2^n)-1, which is an odd >> number if n is any positive integer. In other words, the following >> statements cannot all be true at once: >> >> 1) Every bit pattern represents a different value. >> 2) There is a bit pattern that represents zero. >> 3) The number of distinct positive values is equal to the number of >> distinct negative values. > > I was more concerned about why there is an > unevenness across the interval. You have > more negative values than positive values. > > So if we consider n = 3 and twos complement, > then: > > 101 = -3 > 110 = -2 > 111 = -1 > 000 = 0 > 001 = 1 > 010 = 2 > 011 = 3 > > And then we elect to have > 4, 100, be represented by > our remaining bit pattern > and to interpret it as a > negative four. It seems like > it could have been just as well > to choose to interpret that > bit pattern as a positive four. > Therefore, the unevenness of this > interval seems to be an arbitrary > choice. > > So instead of having our > interval defined as follows: > [-(2^(n - 1)-1), (2^(n - 1)] > We arbitrarily choose to > have it defined as follows: > [-(2^(n - 1)), 2^(n-1)-1] > > In the case of n = 3 > > Instead of > [-3, 4] > We get: > [-4, 3] > > Am I off base or is this > seemingly arbitrary choice > the reasoning behind this > unnevenness? If you did it your way, what would be involved in detecting if a number was negative or not? Right now, we check the sign bit. If the sign bit is set, the number is negative, no matter the rest of the bits. Each check, fast to do. With your method you now put in a special case for 10000.. which has to be supported in the code, in the CPU, in programs, etc... just so you get one extra number out of an integer. There is no way it is worth it. The sign bit is a lot easier, if it's set, the number is negative. If it's not set, the number is positive. Period. There's an old axiom, KISS used in Bridge. Every Bridge player knows it. It means "Keep It Simple Stupid" -- Jim Langston tazmaster(a)rocketmail.com
From: Jerry Coffin on 13 Jan 2008 01:46 In article <6422059c-2d8f-4d16-82ea- 850a1f181e5a(a)l32g2000hse.googlegroups.com>, conrad(a)lawyer.com says... [ ... ] > I was more concerned about why there is an > unevenness across the interval. You have > more negative values than positive values. > > So if we consider n = 3 and twos complement, > then: > > 101 = -3 > 110 = -2 > 111 = -1 > 000 = 0 > 001 = 1 > 010 = 2 > 011 = 3 > > And then we elect to have > 4, 100, be represented by > our remaining bit pattern > and to interpret it as a > negative four. Yes, we could, but it would make life miserable in general. The use of the sign bit has already been mentioned. More importantly, is how all this is implemented in real hardware. As it stands right now, an adder is a fairly simple device. A half adder takes two bits of input, and produces two bits of output (the current bit and the carry bit). The carry bit is produced by the and of the two inputs, and the current bit is the xor of the two inputs. IOW, a half adder takes two gates. A full adder takes three inputs (two bits from the items being added, plus the carry from the previous bit). A full adder is marginally more complex than a half adder, but it's still pretty small and takes only a couple of gates. An adder for signed or unsigned numbers uses identical circuits and on a bitwise basis produces identical results -- the signedness or lack of it exists only in how those bit patterns are interpreted. With twos complement, subtracting is done by adding the negative of a number. Negating a number is trivial as well -- complement all the bits, then increment the result. Your idea would change all that -- the adder for signed and unsigned numbers would be entirely different from each other. Worse, the adder for signed numbers would be considerably more complex, because it'd involve some special case code. Subtracting would be ugly as well (it'd be even uglier, since you've have ugly negation followed by ugly addition). > It seems like > it could have been just as well > to choose to interpret that > bit pattern as a positive four. > Therefore, the unevenness of this > interval seems to be an arbitrary > choice. You could IF you could find some circuitry that made it easy and efficient to do so. Remember that in the end, what was ask out of the computer has to be implemented in real hardware. If you want an idea of what's needed, write some code to implement the basic operations (addition, subtraction, multiplication and division) using the operations available at the hardware level (AND, OR and NOT gates ONLY). For a given technology, the maximum clock rate for a design is governed largely by the maximum number of gates from the beginning to end of a single pipeline stage. Assuming you want single-cycle addition like every other CPU does any more, the number of gates from beginning to end can govern your maximum clock speed. If (for example) your number system requires 30% more gates from beginning to end, that translates quite directly to roughly 30% slower clock speed in the same technology. -- Later, Jerry. The universe is a figment of its own imagination.
From: Ulrich Eckhardt on 13 Jan 2008 05:09
conrad wrote: > On Jan 12, 12:18�pm, "Andrew Koenig" <a...(a)acm.org> wrote: >> [about binary numbers ] >> In other words, the following statements cannot all be >> true at once: >> >> 1) Every bit pattern represents a different value. >> 2) There is a bit pattern that represents zero. >> 3) The number of distinct positive values is equal to the number of >> distinct negative values. > > I was more concerned about why there is an > unevenness across the interval. You have > more negative values than positive values. > > So if we consider n = 3 and twos complement, > then: > > 101 = -3 > 110 = -2 > 111 = -1 > 000 = 0 > 001 = 1 > 010 = 2 > 011 = 3 > > And then we elect to have 4, 100, be represented by our remaining > bit pattern and to interpret it as a negative four. It seems like > it could have been just as well to choose to interpret that bit > pattern as a positive four. Therefore, the unevenness of this > interval seems to be an arbitrary choice. The 'unevenness' you perceive isn't there if you look at it from a different angle. Firstly, take a look at the signed and unsigned interpretations of such a number: bin unsigned signed 000 0 0 001 1 1 010 2 2 011 3 3 100 4 -4 101 5 -3 110 6 -2 111 7 -1 First thing you see is that (with the exception 011/100) the difference between each neighbouring values is exactly 1. Concerning the wraparound of limited-size integers, it is in fact always the case, only that the wraparound happens in the middle for signed numbers. This means for example that you can use the exact same hardware to calculate the difference or sum between two integers, regardless of whether they are signed or not. Another thing you can observe (and I personally find this explanation better than the one using a "sign bit") is that you could also say that apart from its value (4), the highest bit in signed numbers also has a negative sign, i.e. its value is actually -4. This is opposed to the way the sign bit works in sign/magnitude binaries, where it affects the sign of the whole number, which is also the reason I object to calling it the sign bit (yes, you can see the sign of the overall number from the highest bit, but that's not all it signals). > Am I off base or is this seemingly arbitrary choice > the reasoning behind this unnevenness? No you are not off base. However, what I think you don't consider or what you are not sufficiently aware of is the fact that computers are still made up of simple logic gates like AND, OR or NOT. Using those as basic building blocks[1], implementing operations like addition or subtraction become more or less easy to implement, hence the choice to do things like they are currently still done. HTH Uli [1] Note: In fact the most basic building block is a NAND gate because it only consists of two transistors. You can build any other gate (OR, NOT, EOR etc) on top of it. Further, you can also create things like flip-flops and other high-level constructs from it. |