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