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 { 231 z.Add(z, intOne) 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 { 253 z.Add(z, y0) 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 { 282 z.Add(z, intOne) 283 m.Sub(m, y0) 284 } else { 285 z.Sub(z, intOne) 286 m.Add(m, y0) 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 437 // print number as [left pad][sign][prefix][zero pad][digits][right pad] 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: 469 r.UnreadRune() 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 621 X.Add(X, lastX) 622 lastX.Set(temp) 623 624 temp.Set(Y) 625 Y.Mul(Y, q) 626 Y.neg = !Y.neg 627 Y.Add(Y, lastY) 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 { 669 z.Add(z, p) 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 }