The Go Programming Language

Source file src/pkg/big/int.go

     1	// Copyright 2009 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	// This file implements signed multi-precision integers.
     6	
     7	package big
     8	
     9	import (
    10		"fmt"
    11		"io"
    12		"os"
    13		"rand"
    14		"strings"
    15	)
    16	
    17	// An Int represents a signed multi-precision integer.
    18	// The zero value for an Int represents the value 0.
    19	type Int struct {
    20		neg bool // sign
    21		abs nat  // absolute value of the integer
    22	}
    23	
    24	var intOne = &Int{false, natOne}
    25	
    26	// Sign returns:
    27	//
    28	//	-1 if x <  0
    29	//	 0 if x == 0
    30	//	+1 if x >  0
    31	//
    32	func (x *Int) Sign() int {
    33		if len(x.abs) == 0 {
    34			return 0
    35		}
    36		if x.neg {
    37			return -1
    38		}
    39		return 1
    40	}
    41	
    42	// SetInt64 sets z to x and returns z.
    43	func (z *Int) SetInt64(x int64) *Int {
    44		neg := false
    45		if x < 0 {
    46			neg = true
    47			x = -x
    48		}
    49		z.abs = z.abs.setUint64(uint64(x))
    50		z.neg = neg
    51		return z
    52	}
    53	
    54	// NewInt allocates and returns a new Int set to x.
    55	func NewInt(x int64) *Int {
    56		return new(Int).SetInt64(x)
    57	}
    58	
    59	// Set sets z to x and returns z.
    60	func (z *Int) Set(x *Int) *Int {
    61		z.abs = z.abs.set(x.abs)
    62		z.neg = x.neg
    63		return z
    64	}
    65	
    66	// Abs sets z to |x| (the absolute value of x) and returns z.
    67	func (z *Int) Abs(x *Int) *Int {
    68		z.abs = z.abs.set(x.abs)
    69		z.neg = false
    70		return z
    71	}
    72	
    73	// Neg sets z to -x and returns z.
    74	func (z *Int) Neg(x *Int) *Int {
    75		z.abs = z.abs.set(x.abs)
    76		z.neg = len(z.abs) > 0 && !x.neg // 0 has no sign
    77		return z
    78	}
    79	
    80	// Add sets z to the sum x+y and returns z.
    81	func (z *Int) Add(x, y *Int) *Int {
    82		neg := x.neg
    83		if x.neg == y.neg {
    84			// x + y == x + y
    85			// (-x) + (-y) == -(x + y)
    86			z.abs = z.abs.add(x.abs, y.abs)
    87		} else {
    88			// x + (-y) == x - y == -(y - x)
    89			// (-x) + y == y - x == -(x - y)
    90			if x.abs.cmp(y.abs) >= 0 {
    91				z.abs = z.abs.sub(x.abs, y.abs)
    92			} else {
    93				neg = !neg
    94				z.abs = z.abs.sub(y.abs, x.abs)
    95			}
    96		}
    97		z.neg = len(z.abs) > 0 && neg // 0 has no sign
    98		return z
    99	}
   100	
   101	// Sub sets z to the difference x-y and returns z.
   102	func (z *Int) Sub(x, y *Int) *Int {
   103		neg := x.neg
   104		if x.neg != y.neg {
   105			// x - (-y) == x + y
   106			// (-x) - y == -(x + y)
   107			z.abs = z.abs.add(x.abs, y.abs)
   108		} else {
   109			// x - y == x - y == -(y - x)
   110			// (-x) - (-y) == y - x == -(x - y)
   111			if x.abs.cmp(y.abs) >= 0 {
   112				z.abs = z.abs.sub(x.abs, y.abs)
   113			} else {
   114				neg = !neg
   115				z.abs = z.abs.sub(y.abs, x.abs)
   116			}
   117		}
   118		z.neg = len(z.abs) > 0 && neg // 0 has no sign
   119		return z
   120	}
   121	
   122	// Mul sets z to the product x*y and returns z.
   123	func (z *Int) Mul(x, y *Int) *Int {
   124		// x * y == x * y
   125		// x * (-y) == -(x * y)
   126		// (-x) * y == -(x * y)
   127		// (-x) * (-y) == x * y
   128		z.abs = z.abs.mul(x.abs, y.abs)
   129		z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
   130		return z
   131	}
   132	
   133	// MulRange sets z to the product of all integers
   134	// in the range [a, b] inclusively and returns z.
   135	// If a > b (empty range), the result is 1.
   136	func (z *Int) MulRange(a, b int64) *Int {
   137		switch {
   138		case a > b:
   139			return z.SetInt64(1) // empty range
   140		case a <= 0 && b >= 0:
   141			return z.SetInt64(0) // range includes 0
   142		}
   143		// a <= b && (b < 0 || a > 0)
   144	
   145		neg := false
   146		if a < 0 {
   147			neg = (b-a)&1 == 0
   148			a, b = -b, -a
   149		}
   150	
   151		z.abs = z.abs.mulRange(uint64(a), uint64(b))
   152		z.neg = neg
   153		return z
   154	}
   155	
   156	// Binomial sets z to the binomial coefficient of (n, k) and returns z.
   157	func (z *Int) Binomial(n, k int64) *Int {
   158		var a, b Int
   159		a.MulRange(n-k+1, n)
   160		b.MulRange(1, k)
   161		return z.Quo(&a, &b)
   162	}
   163	
   164	// Quo sets z to the quotient x/y for y != 0 and returns z.
   165	// If y == 0, a division-by-zero run-time panic occurs.
   166	// See QuoRem for more details.
   167	func (z *Int) Quo(x, y *Int) *Int {
   168		z.abs, _ = z.abs.div(nil, x.abs, y.abs)
   169		z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
   170		return z
   171	}
   172	
   173	// Rem sets z to the remainder x%y for y != 0 and returns z.
   174	// If y == 0, a division-by-zero run-time panic occurs.
   175	// See QuoRem for more details.
   176	func (z *Int) Rem(x, y *Int) *Int {
   177		_, z.abs = nat(nil).div(z.abs, x.abs, y.abs)
   178		z.neg = len(z.abs) > 0 && x.neg // 0 has no sign
   179		return z
   180	}
   181	
   182	// QuoRem sets z to the quotient x/y and r to the remainder x%y
   183	// and returns the pair (z, r) for y != 0.
   184	// If y == 0, a division-by-zero run-time panic occurs.
   185	//
   186	// QuoRem implements T-division and modulus (like Go):
   187	//
   188	//	q = x/y      with the result truncated to zero
   189	//	r = x - y*q
   190	//
   191	// (See Daan Leijen, ``Division and Modulus for Computer Scientists''.)
   192	//
   193	func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) {
   194		z.abs, r.abs = z.abs.div(r.abs, x.abs, y.abs)
   195		z.neg, r.neg = len(z.abs) > 0 && x.neg != y.neg, len(r.abs) > 0 && x.neg // 0 has no sign
   196		return z, r
   197	}
   198	
   199	// Div sets z to the quotient x/y for y != 0 and returns z.
   200	// If y == 0, a division-by-zero run-time panic occurs.
   201	// See DivMod for more details.
   202	func (z *Int) Div(x, y *Int) *Int {
   203		y_neg := y.neg // z may be an alias for y
   204		var r Int
   205		z.QuoRem(x, y, &r)
   206		if r.neg {
   207			if y_neg {
   208				z.Add(z, intOne)
   209			} else {
   210				z.Sub(z, intOne)
   211			}
   212		}
   213		return z
   214	}
   215	
   216	// Mod sets z to the modulus x%y for y != 0 and returns z.
   217	// If y == 0, a division-by-zero run-time panic occurs.
   218	// See DivMod for more details.
   219	func (z *Int) Mod(x, y *Int) *Int {
   220		y0 := y // save y
   221		if z == y || alias(z.abs, y.abs) {
   222			y0 = new(Int).Set(y)
   223		}
   224		var q Int
   225		q.QuoRem(x, y, z)
   226		if z.neg {
   227			if y0.neg {
   228				z.Sub(z, y0)
   229			} else {
   230				z.Add(z, y0)
   231			}
   232		}
   233		return z
   234	}
   235	
   236	// DivMod sets z to the quotient x div y and m to the modulus x mod y
   237	// and returns the pair (z, m) for y != 0.
   238	// If y == 0, a division-by-zero run-time panic occurs.
   239	//
   240	// DivMod implements Euclidean division and modulus (unlike Go):
   241	//
   242	//	q = x div y  such that
   243	//	m = x - y*q  with 0 <= m < |q|
   244	//
   245	// (See Raymond T. Boute, ``The Euclidean definition of the functions
   246	// div and mod''. ACM Transactions on Programming Languages and
   247	// Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992.
   248	// ACM press.)
   249	//
   250	func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) {
   251		y0 := y // save y
   252		if z == y || alias(z.abs, y.abs) {
   253			y0 = new(Int).Set(y)
   254		}
   255		z.QuoRem(x, y, m)
   256		if m.neg {
   257			if y0.neg {
   258				z.Add(z, intOne)
   259				m.Sub(m, y0)
   260			} else {
   261				z.Sub(z, intOne)
   262				m.Add(m, y0)
   263			}
   264		}
   265		return z, m
   266	}
   267	
   268	// Cmp compares x and y and returns:
   269	//
   270	//   -1 if x <  y
   271	//    0 if x == y
   272	//   +1 if x >  y
   273	//
   274	func (x *Int) Cmp(y *Int) (r int) {
   275		// x cmp y == x cmp y
   276		// x cmp (-y) == x
   277		// (-x) cmp y == y
   278		// (-x) cmp (-y) == -(x cmp y)
   279		switch {
   280		case x.neg == y.neg:
   281			r = x.abs.cmp(y.abs)
   282			if x.neg {
   283				r = -r
   284			}
   285		case x.neg:
   286			r = -1
   287		default:
   288			r = 1
   289		}
   290		return
   291	}
   292	
   293	func (x *Int) String() string {
   294		switch {
   295		case x == nil:
   296			return "<nil>"
   297		case x.neg:
   298			return "-" + x.abs.decimalString()
   299		}
   300		return x.abs.decimalString()
   301	}
   302	
   303	func charset(ch int) string {
   304		switch ch {
   305		case 'b':
   306			return lowercaseDigits[0:2]
   307		case 'o':
   308			return lowercaseDigits[0:8]
   309		case 'd', 's', 'v':
   310			return lowercaseDigits[0:10]
   311		case 'x':
   312			return lowercaseDigits[0:16]
   313		case 'X':
   314			return uppercaseDigits[0:16]
   315		}
   316		return "" // unknown format
   317	}
   318	
   319	// write count copies of text to s
   320	func writeMultiple(s fmt.State, text string, count int) {
   321		if len(text) > 0 {
   322			b := []byte(text)
   323			for ; count > 0; count-- {
   324				s.Write(b)
   325			}
   326		}
   327	}
   328	
   329	// Format is a support routine for fmt.Formatter. It accepts
   330	// the formats 'b' (binary), 'o' (octal), 'd' (decimal), 'x'
   331	// (lowercase hexadecimal), and 'X' (uppercase hexadecimal).
   332	// Also supported are the full suite of package fmt's format
   333	// verbs for integral types, including '+', '-', and ' '
   334	// for sign control, '#' for leading zero in octal and for
   335	// hexadecimal, a leading "0x" or "0X" for "%#x" and "%#X"
   336	// respectively, specification of minimum digits precision,
   337	// output field width, space or zero padding, and left or
   338	// right justification.
   339	//
   340	func (x *Int) Format(s fmt.State, ch int) {
   341		cs := charset(ch)
   342	
   343		// special cases
   344		switch {
   345		case cs == "":
   346			// unknown format
   347			fmt.Fprintf(s, "%%!%c(big.Int=%s)", ch, x.String())
   348			return
   349		case x == nil:
   350			fmt.Fprint(s, "<nil>")
   351			return
   352		}
   353	
   354		// determine sign character
   355		sign := ""
   356		switch {
   357		case x.neg:
   358			sign = "-"
   359		case s.Flag('+'): // supersedes ' ' when both specified
   360			sign = "+"
   361		case s.Flag(' '):
   362			sign = " "
   363		}
   364	
   365		// determine prefix characters for indicating output base
   366		prefix := ""
   367		if s.Flag('#') {
   368			switch ch {
   369			case 'o': // octal
   370				prefix = "0"
   371			case 'x': // hexadecimal
   372				prefix = "0x"
   373			case 'X':
   374				prefix = "0X"
   375			}
   376		}
   377	
   378		// determine digits with base set by len(cs) and digit characters from cs
   379		digits := x.abs.string(cs)
   380	
   381		// number of characters for the three classes of number padding
   382		var left int   // space characters to left of digits for right justification ("%8d")
   383		var zeroes int // zero characters (actually cs[0]) as left-most digits ("%.8d")
   384		var right int  // space characters to right of digits for left justification ("%-8d")
   385	
   386		// determine number padding from precision: the least number of digits to output
   387		precision, precisionSet := s.Precision()
   388		if precisionSet {
   389			switch {
   390			case len(digits) < precision:
   391				zeroes = precision - len(digits) // count of zero padding 
   392			case digits == "0" && precision == 0:
   393				return // print nothing if zero value (x == 0) and zero precision ("." or ".0")
   394			}
   395		}
   396	
   397		// determine field pad from width: the least number of characters to output
   398		length := len(sign) + len(prefix) + zeroes + len(digits)
   399		if width, widthSet := s.Width(); widthSet && length < width { // pad as specified
   400			switch d := width - length; {
   401			case s.Flag('-'):
   402				// pad on the right with spaces; supersedes '0' when both specified
   403				right = d
   404			case s.Flag('0') && !precisionSet:
   405				// pad with zeroes unless precision also specified
   406				zeroes = d
   407			default:
   408				// pad on the left with spaces
   409				left = d
   410			}
   411		}
   412	
   413		// print number as [left pad][sign][prefix][zero pad][digits][right pad]
   414		writeMultiple(s, " ", left)
   415		writeMultiple(s, sign, 1)
   416		writeMultiple(s, prefix, 1)
   417		writeMultiple(s, "0", zeroes)
   418		writeMultiple(s, digits, 1)
   419		writeMultiple(s, " ", right)
   420	}
   421	
   422	// scan sets z to the integer value corresponding to the longest possible prefix
   423	// read from r representing a signed integer number in a given conversion base.
   424	// It returns z, the actual conversion base used, and an error, if any. In the
   425	// error case, the value of z is undefined. The syntax follows the syntax of
   426	// integer literals in Go.
   427	//
   428	// The base argument must be 0 or a value from 2 through MaxBase. If the base
   429	// is 0, the string prefix determines the actual conversion base. A prefix of
   430	// ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a
   431	// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
   432	//
   433	func (z *Int) scan(r io.RuneScanner, base int) (*Int, int, os.Error) {
   434		// determine sign
   435		ch, _, err := r.ReadRune()
   436		if err != nil {
   437			return z, 0, err
   438		}
   439		neg := false
   440		switch ch {
   441		case '-':
   442			neg = true
   443		case '+': // nothing to do
   444		default:
   445			r.UnreadRune()
   446		}
   447	
   448		// determine mantissa
   449		z.abs, base, err = z.abs.scan(r, base)
   450		if err != nil {
   451			return z, base, err
   452		}
   453		z.neg = len(z.abs) > 0 && neg // 0 has no sign
   454	
   455		return z, base, nil
   456	}
   457	
   458	// Scan is a support routine for fmt.Scanner; it sets z to the value of
   459	// the scanned number. It accepts the formats 'b' (binary), 'o' (octal),
   460	// 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal).
   461	func (z *Int) Scan(s fmt.ScanState, ch int) os.Error {
   462		s.SkipSpace() // skip leading space characters
   463		base := 0
   464		switch ch {
   465		case 'b':
   466			base = 2
   467		case 'o':
   468			base = 8
   469		case 'd':
   470			base = 10
   471		case 'x', 'X':
   472			base = 16
   473		case 's', 'v':
   474			// let scan determine the base
   475		default:
   476			return os.NewError("Int.Scan: invalid verb")
   477		}
   478		_, _, err := z.scan(s, base)
   479		return err
   480	}
   481	
   482	// Int64 returns the int64 representation of x.
   483	// If x cannot be represented in an int64, the result is undefined.
   484	func (x *Int) Int64() int64 {
   485		if len(x.abs) == 0 {
   486			return 0
   487		}
   488		v := int64(x.abs[0])
   489		if _W == 32 && len(x.abs) > 1 {
   490			v |= int64(x.abs[1]) << 32
   491		}
   492		if x.neg {
   493			v = -v
   494		}
   495		return v
   496	}
   497	
   498	// SetString sets z to the value of s, interpreted in the given base,
   499	// and returns z and a boolean indicating success. If SetString fails,
   500	// the value of z is undefined.
   501	//
   502	// The base argument must be 0 or a value from 2 through MaxBase. If the base
   503	// is 0, the string prefix determines the actual conversion base. A prefix of
   504	// ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a
   505	// ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
   506	//
   507	func (z *Int) SetString(s string, base int) (*Int, bool) {
   508		r := strings.NewReader(s)
   509		_, _, err := z.scan(r, base)
   510		if err != nil {
   511			return z, false
   512		}
   513		_, _, err = r.ReadRune()
   514		return z, err == os.EOF // err == os.EOF => scan consumed all of s
   515	}
   516	
   517	// SetBytes interprets buf as the bytes of a big-endian unsigned
   518	// integer, sets z to that value, and returns z.
   519	func (z *Int) SetBytes(buf []byte) *Int {
   520		z.abs = z.abs.setBytes(buf)
   521		z.neg = false
   522		return z
   523	}
   524	
   525	// Bytes returns the absolute value of z as a big-endian byte slice.
   526	func (z *Int) Bytes() []byte {
   527		buf := make([]byte, len(z.abs)*_S)
   528		return buf[z.abs.bytes(buf):]
   529	}
   530	
   531	// BitLen returns the length of the absolute value of z in bits.
   532	// The bit length of 0 is 0.
   533	func (z *Int) BitLen() int {
   534		return z.abs.bitLen()
   535	}
   536	
   537	// Exp sets z = x**y mod m. If m is nil, z = x**y.
   538	// See Knuth, volume 2, section 4.6.3.
   539	func (z *Int) Exp(x, y, m *Int) *Int {
   540		if y.neg || len(y.abs) == 0 {
   541			neg := x.neg
   542			z.SetInt64(1)
   543			z.neg = neg
   544			return z
   545		}
   546	
   547		var mWords nat
   548		if m != nil {
   549			mWords = m.abs
   550		}
   551	
   552		z.abs = z.abs.expNN(x.abs, y.abs, mWords)
   553		z.neg = len(z.abs) > 0 && x.neg && y.abs[0]&1 == 1 // 0 has no sign
   554		return z
   555	}
   556	
   557	// GcdInt sets d to the greatest common divisor of a and b, which must be
   558	// positive numbers.
   559	// If x and y are not nil, GcdInt sets x and y such that d = a*x + b*y.
   560	// If either a or b is not positive, GcdInt sets d = x = y = 0.
   561	func GcdInt(d, x, y, a, b *Int) {
   562		if a.neg || b.neg {
   563			d.SetInt64(0)
   564			if x != nil {
   565				x.SetInt64(0)
   566			}
   567			if y != nil {
   568				y.SetInt64(0)
   569			}
   570			return
   571		}
   572	
   573		A := new(Int).Set(a)
   574		B := new(Int).Set(b)
   575	
   576		X := new(Int)
   577		Y := new(Int).SetInt64(1)
   578	
   579		lastX := new(Int).SetInt64(1)
   580		lastY := new(Int)
   581	
   582		q := new(Int)
   583		temp := new(Int)
   584	
   585		for len(B.abs) > 0 {
   586			r := new(Int)
   587			q, r = q.QuoRem(A, B, r)
   588	
   589			A, B = B, r
   590	
   591			temp.Set(X)
   592			X.Mul(X, q)
   593			X.neg = !X.neg
   594			X.Add(X, lastX)
   595			lastX.Set(temp)
   596	
   597			temp.Set(Y)
   598			Y.Mul(Y, q)
   599			Y.neg = !Y.neg
   600			Y.Add(Y, lastY)
   601			lastY.Set(temp)
   602		}
   603	
   604		if x != nil {
   605			*x = *lastX
   606		}
   607	
   608		if y != nil {
   609			*y = *lastY
   610		}
   611	
   612		*d = *A
   613	}
   614	
   615	// ProbablyPrime performs n Miller-Rabin tests to check whether z is prime.
   616	// If it returns true, z is prime with probability 1 - 1/4^n.
   617	// If it returns false, z is not prime.
   618	func ProbablyPrime(z *Int, n int) bool {
   619		return !z.neg && z.abs.probablyPrime(n)
   620	}
   621	
   622	// Rand sets z to a pseudo-random number in [0, n) and returns z.
   623	func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
   624		z.neg = false
   625		if n.neg == true || len(n.abs) == 0 {
   626			z.abs = nil
   627			return z
   628		}
   629		z.abs = z.abs.random(rnd, n.abs, n.abs.bitLen())
   630		return z
   631	}
   632	
   633	// ModInverse sets z to the multiplicative inverse of g in the group ℤ/pℤ (where
   634	// p is a prime) and returns z.
   635	func (z *Int) ModInverse(g, p *Int) *Int {
   636		var d Int
   637		GcdInt(&d, z, nil, g, p)
   638		// x and y are such that g*x + p*y = d. Since p is prime, d = 1. Taking
   639		// that modulo p results in g*x = 1, therefore x is the inverse element.
   640		if z.neg {
   641			z.Add(z, p)
   642		}
   643		return z
   644	}
   645	
   646	// Lsh sets z = x << n and returns z.
   647	func (z *Int) Lsh(x *Int, n uint) *Int {
   648		z.abs = z.abs.shl(x.abs, n)
   649		z.neg = x.neg
   650		return z
   651	}
   652	
   653	// Rsh sets z = x >> n and returns z.
   654	func (z *Int) Rsh(x *Int, n uint) *Int {
   655		if x.neg {
   656			// (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1)
   657			t := z.abs.sub(x.abs, natOne) // no underflow because |x| > 0
   658			t = t.shr(t, n)
   659			z.abs = t.add(t, natOne)
   660			z.neg = true // z cannot be zero if x is negative
   661			return z
   662		}
   663	
   664		z.abs = z.abs.shr(x.abs, n)
   665		z.neg = false
   666		return z
   667	}
   668	
   669	// Bit returns the value of the i'th bit of z. That is, it
   670	// returns (z>>i)&1. The bit index i must be >= 0.
   671	func (z *Int) Bit(i int) uint {
   672		if i < 0 {
   673			panic("negative bit index")
   674		}
   675		if z.neg {
   676			t := nat{}.sub(z.abs, natOne)
   677			return t.bit(uint(i)) ^ 1
   678		}
   679	
   680		return z.abs.bit(uint(i))
   681	}
   682	
   683	// SetBit sets the i'th bit of z to bit and returns z.
   684	// That is, if bit is 1 SetBit sets z = x | (1 << i);
   685	// if bit is 0 it sets z = x &^ (1 << i). If bit is not 0 or 1,
   686	// SetBit will panic.
   687	func (z *Int) SetBit(x *Int, i int, b uint) *Int {
   688		if i < 0 {
   689			panic("negative bit index")
   690		}
   691		if x.neg {
   692			t := z.abs.sub(x.abs, natOne)
   693			t = t.setBit(t, uint(i), b^1)
   694			z.abs = t.add(t, natOne)
   695			z.neg = len(z.abs) > 0
   696			return z
   697		}
   698		z.abs = z.abs.setBit(x.abs, uint(i), b)
   699		z.neg = false
   700		return z
   701	}
   702	
   703	// And sets z = x & y and returns z.
   704	func (z *Int) And(x, y *Int) *Int {
   705		if x.neg == y.neg {
   706			if x.neg {
   707				// (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
   708				x1 := nat{}.sub(x.abs, natOne)
   709				y1 := nat{}.sub(y.abs, natOne)
   710				z.abs = z.abs.add(z.abs.or(x1, y1), natOne)
   711				z.neg = true // z cannot be zero if x and y are negative
   712				return z
   713			}
   714	
   715			// x & y == x & y
   716			z.abs = z.abs.and(x.abs, y.abs)
   717			z.neg = false
   718			return z
   719		}
   720	
   721		// x.neg != y.neg
   722		if x.neg {
   723			x, y = y, x // & is symmetric
   724		}
   725	
   726		// x & (-y) == x & ^(y-1) == x &^ (y-1)
   727		y1 := nat{}.sub(y.abs, natOne)
   728		z.abs = z.abs.andNot(x.abs, y1)
   729		z.neg = false
   730		return z
   731	}
   732	
   733	// AndNot sets z = x &^ y and returns z.
   734	func (z *Int) AndNot(x, y *Int) *Int {
   735		if x.neg == y.neg {
   736			if x.neg {
   737				// (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
   738				x1 := nat{}.sub(x.abs, natOne)
   739				y1 := nat{}.sub(y.abs, natOne)
   740				z.abs = z.abs.andNot(y1, x1)
   741				z.neg = false
   742				return z
   743			}
   744	
   745			// x &^ y == x &^ y
   746			z.abs = z.abs.andNot(x.abs, y.abs)
   747			z.neg = false
   748			return z
   749		}
   750	
   751		if x.neg {
   752			// (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
   753			x1 := nat{}.sub(x.abs, natOne)
   754			z.abs = z.abs.add(z.abs.or(x1, y.abs), natOne)
   755			z.neg = true // z cannot be zero if x is negative and y is positive
   756			return z
   757		}
   758	
   759		// x &^ (-y) == x &^ ^(y-1) == x & (y-1)
   760		y1 := nat{}.add(y.abs, natOne)
   761		z.abs = z.abs.and(x.abs, y1)
   762		z.neg = false
   763		return z
   764	}
   765	
   766	// Or sets z = x | y and returns z.
   767	func (z *Int) Or(x, y *Int) *Int {
   768		if x.neg == y.neg {
   769			if x.neg {
   770				// (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
   771				x1 := nat{}.sub(x.abs, natOne)
   772				y1 := nat{}.sub(y.abs, natOne)
   773				z.abs = z.abs.add(z.abs.and(x1, y1), natOne)
   774				z.neg = true // z cannot be zero if x and y are negative
   775				return z
   776			}
   777	
   778			// x | y == x | y
   779			z.abs = z.abs.or(x.abs, y.abs)
   780			z.neg = false
   781			return z
   782		}
   783	
   784		// x.neg != y.neg
   785		if x.neg {
   786			x, y = y, x // | is symmetric
   787		}
   788	
   789		// x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
   790		y1 := nat{}.sub(y.abs, natOne)
   791		z.abs = z.abs.add(z.abs.andNot(y1, x.abs), natOne)
   792		z.neg = true // z cannot be zero if one of x or y is negative
   793		return z
   794	}
   795	
   796	// Xor sets z = x ^ y and returns z.
   797	func (z *Int) Xor(x, y *Int) *Int {
   798		if x.neg == y.neg {
   799			if x.neg {
   800				// (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
   801				x1 := nat{}.sub(x.abs, natOne)
   802				y1 := nat{}.sub(y.abs, natOne)
   803				z.abs = z.abs.xor(x1, y1)
   804				z.neg = false
   805				return z
   806			}
   807	
   808			// x ^ y == x ^ y
   809			z.abs = z.abs.xor(x.abs, y.abs)
   810			z.neg = false
   811			return z
   812		}
   813	
   814		// x.neg != y.neg
   815		if x.neg {
   816			x, y = y, x // ^ is symmetric
   817		}
   818	
   819		// x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
   820		y1 := nat{}.sub(y.abs, natOne)
   821		z.abs = z.abs.add(z.abs.xor(x.abs, y1), natOne)
   822		z.neg = true // z cannot be zero if only one of x or y is negative
   823		return z
   824	}
   825	
   826	// Not sets z = ^x and returns z.
   827	func (z *Int) Not(x *Int) *Int {
   828		if x.neg {
   829			// ^(-x) == ^(^(x-1)) == x-1
   830			z.abs = z.abs.sub(x.abs, natOne)
   831			z.neg = false
   832			return z
   833		}
   834	
   835		// ^x == -x-1 == -(x+1)
   836		z.abs = z.abs.add(x.abs, natOne)
   837		z.neg = true // z cannot be zero if x is positive
   838		return z
   839	}
   840	
   841	// Gob codec version. Permits backward-compatible changes to the encoding.
   842	const intGobVersion byte = 1
   843	
   844	// GobEncode implements the gob.GobEncoder interface.
   845	func (z *Int) GobEncode() ([]byte, os.Error) {
   846		buf := make([]byte, 1+len(z.abs)*_S) // extra byte for version and sign bit
   847		i := z.abs.bytes(buf) - 1            // i >= 0
   848		b := intGobVersion << 1              // make space for sign bit
   849		if z.neg {
   850			b |= 1
   851		}
   852		buf[i] = b
   853		return buf[i:], nil
   854	}
   855	
   856	// GobDecode implements the gob.GobDecoder interface.
   857	func (z *Int) GobDecode(buf []byte) os.Error {
   858		if len(buf) == 0 {
   859			return os.NewError("Int.GobDecode: no data")
   860		}
   861		b := buf[0]
   862		if b>>1 != intGobVersion {
   863			return os.NewError(fmt.Sprintf("Int.GobDecode: encoding version %d not supported", b>>1))
   864		}
   865		z.neg = b&1 != 0
   866		z.abs = z.abs.setBytes(buf[1:])
   867		return nil
   868	}

release.r60.3. Except as noted, this content is licensed under a Creative Commons Attribution 3.0 License.