FACTOID # 22: South Dakota has the highest employment ratio in America, but the lowest median earnings of full-time male employees.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Negabinary" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Negabinary

'Negabinary' (radix -2) is a fairly obscure numeral system used in the experimental Polish computers SKRZAT 1 and BINEG in 1950. It has the unusual property that negative and positive numbers can be represented without a sign bit, although arithmetic operations are more complicated. roger la crevette A numeral is a symbol or group of symbols that represents a number. ... 1950 was a common year starting on Sunday (link will take you to calendar). ...

Contents


History

Negative numerical bases were discovered by Vittorio Grunwald in his work Giornale di Matematiche di Battaglini, published in 1885. Grunwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases were later independently rediscovered by A. J. Kempner in 1936 and Z. Pawlak and A. Wakulicz in 1959. 1885 is a common year starting on Thursday. ... 1936 (MCMXXXVI) was a leap year starting on Wednesday (link will take you to calendar). ... 1959 (MCMLIX) was a common year starting on Thursday of the Gregorian calendar. ...


Writing numbers in negabinary

Every integer can be written uniquely in the form The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ...

where each digit dk is either 0 or 1 and the "leading bit" dn is 1 (unless n=0). The negabinary expansion of the given integer is then given by the string dn;dn-1...d1d0. Some negabinary numbers have the same representation in binary. For example,

17 = 42 + 40

and is represented by 10001 in binary and 10001 in negabinary.


The numbers from -5 to 6 with their negabinary expansions are:

 -5 1111 -4 1100 -3 1101 -2 10 -1 11 0 0 1 1 2 110 3 111 4 100 5 101 6 11010 

The negabinary expansion of a number can be found by repeated division by -2, recording the non-negative remainders of 0 or 1, and concatenating those remainders, starting with the last. Note that if a / b = c, remainder d, then bc + d = a. For example:

 13 / -2 = -6, remainder 1 -6 / -2 = 3, remainder 0 3 / -2 = -1, remainder 1 -1 / -2 = 1, remainder 1 1 / -2 = 0, remainder 1 

Therefore, the negabinary expansion of 13 is 11101.


Note that the negabinary expansions of negative integers have an even number of bits, while the negabinary expansions of the non-negative integers have an odd number of bits. In mathematics, any integer (whole number) is either even or odd. ... In mathematics, any integer (whole number) is either even or odd. ...


Addition

To add two negabinary numbers, start with a carry of 0, and, starting from the least significant bits, add the bits of the two numbers plus the carry. The resulting number is then looked up in the following table to get the bit to write down as result, and the next carry: In computing, the least significant bit (LSB) is the bit position in a binary number having the value of 1. ...

 number bit carry -2 0 1 (Note: -2 only occurs during subtraction.) -1 1 1 0 0 0 1 1 0 2 0 -1 3 1 -1 (Note: 3 only occurs during addition.) 

The second row of this table, for instance, expresses the fact that -1 = 1 + 1×(-2); the fifth row says 2 = 0 + -1×(-2); etc.


As an example, to add 1010101 (1+4+16+64 = 85) and 1110100 (4+16-32+64 = 52),

 carry: 1 -1 0 -1 1 -1 0 0 0 first number: 1 0 1 0 1 0 1 second number: 1 1 1 0 1 0 0 + -------------------------- number: 1 -1 2 0 3 -1 2 0 1 bit (result): 1 1 0 0 1 1 0 0 1 carry: 0 1 -1 0 -1 1 -1 0 0 

so the result is 110011001 (1-8+16-128+256 = 137).


Subtraction

To subtract, multiply each bit of the second number by -1, and add the numbers, using the same table as above.


As an example, to compute 1101001 (1-8-32+64 = 25) minus 1110100 (4+16-32+64 = 52),

 carry: 0 1 -1 1 0 0 0 first number: 1 1 0 1 0 0 1 second number: -1 -1 -1 0 -1 0 0 + -------------------- number: 0 1 -2 2 -1 0 1 bit (result): 0 1 0 0 1 0 1 carry: 0 0 1 -1 1 0 0 

so the result is 100101 (1+4-32 = -27).


To negate a number, compute 0 minus the number.


Multiplication and division

Shifting to the left multiplies by -2, shifting to the right divides by -2.


To multiply, multiply like normal decimal or binary numbers, but using the negabinary rules for adding the carry, when adding the numbers. Decimal, or less commonly, denary, usually refers to the base 10 numeral system. ... The binary numeral system represents numeric values using two symbols, typically 0 and 1. ...

 first number: 1 1 1 0 1 1 0 second number: 1 0 1 1 0 1 1 * ------------------------------------- 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 + ------------------------------------- carry: 0 -1 0 -1 -1 -1 -1 -1 0 -1 0 0 number: 1 0 2 1 2 2 2 3 2 0 2 1 0 bit (result): 1 0 0 1 0 0 0 1 0 0 0 1 0 carry: 0 -1 0 -1 -1 -1 -1 -1 0 -1 0 0 

For each column, add carry to number, and divide the sum by -2, to get the new carry, and the resulting bit as the remainder.



See also binary, balanced ternary, numeral system. The binary numeral system represents numeric values using two symbols, typically 0 and 1. ... Ternary is the base-3 numeral system. ... roger la crevette A numeral is a symbol or group of symbols that represents a number. ...


External resources

  • Vittorio Grunwald. Giornale di Matematiche di Battaglini (1885), 203-221, 367
  • A. J. Kempner. (1936), 610-617
  • Z. Pawlek and A. Wakulicz Bulletin de l'Academie Polonaise des Scienses, Classe III, 5 (1957), 233-236; Serie des sciences techniques 7 (1959), 713-721
  • L. Wadel IRE Transactions EC-6 1957, 123
  • N. M. Blachman, Communications of the ACM (1961), 257
  • IEEE Transactions 1963, 274-276
  • Computer Design May 1967, 52-63
  • R. W. Marczynski, Annotated History of Computing, 1980, 37-48
  • D. Knuth. The Art of Computer Programming, Volume 2, 3rd. Ed. pp204-205

  Results from FactBites:
 
Negative Base Numbering Systems (643 words)
Negabinary is a lot like binary’s evil twin.
The beauty of negabinary is that there is no need for a negative sign (aka the sign bit).
To expand a decimal number into negabinary, you simply divide the number by -2 repeatedly.
Negabinary (596 words)
'Negabinary' (radix -2) is a fairly obscure numeral system used in the experimental Poland computers SKRZAT 1[?] and BINEG[?] in 1950.
Numbers can be convered to negabinary by repeated division by -2, recording the remainder of 0 or 1.
To add two negabinary numbers, start with a carry of 0, and, starting from the least significant bits[?], add the bit of each number plus the carry, record the bit of the resulting number and set the carry according to the number.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m