diff options
author | Evan Shaw <chickencha@gmail.com> | 2010-05-03 11:20:52 -0700 |
---|---|---|
committer | Evan Shaw <chickencha@gmail.com> | 2010-05-03 11:20:52 -0700 |
commit | 3fbde649bf006ba61f91a485df6abfd6df020604 (patch) | |
tree | 5089703755a83dd7db41d004e5ed322f060c4fd5 /src/pkg/big | |
parent | 650953965181e651164b1f135b0cd901096b34ef (diff) | |
download | golang-3fbde649bf006ba61f91a485df6abfd6df020604.tar.gz |
big: Add bitwise methods for Int
R=gri
CC=golang-dev
http://codereview.appspot.com/987041
Committer: Robert Griesemer <gri@golang.org>
Diffstat (limited to 'src/pkg/big')
-rwxr-xr-x[-rw-r--r--] | src/pkg/big/int.go | 142 | ||||
-rwxr-xr-x[-rw-r--r--] | src/pkg/big/int_test.go | 126 | ||||
-rwxr-xr-x[-rw-r--r--] | src/pkg/big/nat.go | 77 | ||||
-rwxr-xr-x[-rw-r--r--] | src/pkg/big/nat_test.go | 22 |
4 files changed, 355 insertions, 12 deletions
diff --git a/src/pkg/big/int.go b/src/pkg/big/int.go index 2b7a62805..4d1be5db6 100644..100755 --- a/src/pkg/big/int.go +++ b/src/pkg/big/int.go @@ -408,3 +408,145 @@ func (z *Int) Rsh(x *Int, n uint) *Int { z.abs = z.abs.shr(x.abs, n) return z } + +// And sets z = x & y and returns z. +func (z *Int) And(x, y *Int) *Int { + if x.neg == y.neg { + if x.neg { + // (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1) + x1 := nat{}.sub(x.abs, natOne) + y1 := z.abs.sub(y.abs, natOne) + z.neg = true + z.abs = z.abs.add(z.abs.or(x1, y1), natOne) + return z + } + + // x & y == x & y + z.neg = false + z.abs = z.abs.and(x.abs, y.abs) + return z + } + + // x.neg != y.neg + if x.neg { + x, y = y, x // & is symmetric + } + + // x & (-y) == x & ^(y-1) == x &^ (y-1) + y1 := z.abs.sub(y.abs, natOne) + z.neg = false + z.abs = z.abs.andNot(x.abs, y1) + return z +} + + +// AndNot sets z = x &^ y and returns z. +func (z *Int) AndNot(x, y *Int) *Int { + if x.neg == y.neg { + if x.neg { + // (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1) + x1 := nat{}.sub(x.abs, natOne) + y1 := z.abs.sub(y.abs, natOne) + z.neg = false + z.abs = z.abs.andNot(y1, x1) + return z + } + + // x &^ y == x &^ y + z.neg = false + z.abs = z.abs.andNot(x.abs, y.abs) + return z + } + + if x.neg { + // (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1) + x1 := z.abs.sub(x.abs, natOne) + z.neg = true + z.abs = z.abs.add(z.abs.or(x1, y.abs), natOne) + return z + } + + // x &^ (-y) == x &^ ^(y-1) == x & (y-1) + y1 := z.abs.add(y.abs, natOne) + z.neg = false + z.abs = z.abs.and(x.abs, y1) + return z +} + + +// Or sets z = x | y and returns z. +func (z *Int) Or(x, y *Int) *Int { + if x.neg == y.neg { + if x.neg { + // (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1) + x1 := nat{}.sub(x.abs, natOne) + y1 := z.abs.sub(y.abs, natOne) + z.neg = true + z.abs = z.abs.add(z.abs.and(x1, y1), natOne) + return z + } + + // x | y == x | y + z.neg = false + z.abs = z.abs.or(x.abs, y.abs) + return z + } + + // x.neg != y.neg + if x.neg { + x, y = y, x // | is symmetric + } + + // x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1) + y1 := z.abs.sub(y.abs, natOne) + z.neg = true + z.abs = z.abs.add(z.abs.andNot(y1, x.abs), natOne) + return z +} + + +// Xor sets z = x ^ y and returns z. +func (z *Int) Xor(x, y *Int) *Int { + if x.neg == y.neg { + if x.neg { + // (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1) + x1 := nat{}.sub(x.abs, natOne) + y1 := z.abs.sub(y.abs, natOne) + z.neg = false + z.abs = z.abs.xor(x1, y1) + return z + } + + // x ^ y == x ^ y + z.neg = false + z.abs = z.abs.xor(x.abs, y.abs) + return z + } + + // x.neg != y.neg + if x.neg { + x, y = y, x // | is symmetric + } + + // x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1) + y1 := z.abs.sub(y.abs, natOne) + z.neg = true + z.abs = z.abs.add(z.abs.xor(x.abs, y1), natOne) + return z +} + + +// Not sets z = ^x and returns z. +func (z *Int) Not(x *Int) *Int { + if x.neg { + // ^(-x) == ^(^(x-1)) == x-1 + z.neg = false + z.abs = z.abs.sub(x.abs, natOne) + return z + } + + // ^x == -x-1 == -(x+1) + z.neg = true + z.abs = z.abs.add(x.abs, natOne) + return z +} diff --git a/src/pkg/big/int_test.go b/src/pkg/big/int_test.go index ceb31e069..deacdfac4 100644..100755 --- a/src/pkg/big/int_test.go +++ b/src/pkg/big/int_test.go @@ -709,3 +709,129 @@ func TestInt64(t *testing.T) { } } } + + +type bitwiseTest struct { + x, y string + and, or, xor, andNot string +} + +var bitwiseTests = []bitwiseTest{ + bitwiseTest{"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"}, + bitwiseTest{"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"}, + bitwiseTest{"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"}, + bitwiseTest{"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"}, + bitwiseTest{"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"}, + bitwiseTest{"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"}, + bitwiseTest{"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"}, + bitwiseTest{"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"}, + bitwiseTest{"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"}, + bitwiseTest{"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"}, + bitwiseTest{"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"}, + bitwiseTest{"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"}, + bitwiseTest{ + "0x1000009dc6e3d9822cba04129bcbe3401", + "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd", + "0x1000001186210100001000009048c2001", + "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd", + "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc", + "0x8c40c2d8822caa04120b8321400", + }, + bitwiseTest{ + "0x1000009dc6e3d9822cba04129bcbe3401", + "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd", + "0x8c40c2d8822caa04120b8321401", + "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd", + "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe", + "0x1000001186210100001000009048c2000", + }, + bitwiseTest{ + "-0x1000009dc6e3d9822cba04129bcbe3401", + "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd", + "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd", + "-0x1000001186210100001000009048c2001", + "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc", + "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc", + }, +} + + +type bitFun func(z, x, y *Int) *Int + +func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) { + expected := new(Int) + expected.SetString(exp, 16) + + out := f(new(Int), x, y) + if out.Cmp(expected) != 0 { + println("Test failed") + t.Errorf("%s: got %s want %s", msg, out, expected) + } +} + + +func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) { + expected := new(Int) + expected.SetString(exp, 16) + + x = f(x, x, y) + if x.Cmp(expected) != 0 { + println("Test failed") + t.Errorf("%s: got %s want %s", msg, x, expected) + } +} + + +func TestBitwise(t *testing.T) { + x := new(Int) + y := new(Int) + for _, test := range bitwiseTests { + x.SetString(test.x, 16) + y.SetString(test.y, 16) + + testBitFun(t, "and", (*Int).And, x, y, test.and) + testBitFunSelf(t, "and", (*Int).And, x, y, test.and) + testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot) + testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot) + testBitFun(t, "or", (*Int).Or, x, y, test.or) + testBitFunSelf(t, "or", (*Int).Or, x, y, test.or) + testBitFun(t, "xor", (*Int).Xor, x, y, test.xor) + testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor) + } +} + + +type notTest struct { + in string + out string +} + +var notTests = []notTest{ + notTest{"0", "-1"}, + notTest{"1", "-2"}, + notTest{"7", "-8"}, + notTest{"0", "-1"}, + notTest{"-81910", "81909"}, + notTest{ + "298472983472983471903246121093472394872319615612417471234712061", + "-298472983472983471903246121093472394872319615612417471234712062", + }, +} + +func TestNot(t *testing.T) { + in := new(Int) + out := new(Int) + expected := new(Int) + for i, test := range notTests { + in.SetString(test.in, 10) + expected.SetString(test.out, 10) + out = out.Not(in) + if out.Cmp(expected) != 0 { + t.Errorf("#%d: got %s want %s", i, out, expected) + } + out = out.Not(out) + if out.Cmp(in) != 0 { + t.Errorf("#%d: got %s want %s", i, out, in) + } + } +} diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go index acec53d5b..30ca1e646 100644..100755 --- a/src/pkg/big/nat.go +++ b/src/pkg/big/nat.go @@ -629,7 +629,7 @@ func hexValue(ch byte) int { } -// scanN returns the natural number corresponding to the +// scan returns the natural number corresponding to the // longest possible prefix of s representing a natural number in a // given conversion base, the actual conversion base used, and the // prefix length. The syntax of natural numbers follows the syntax @@ -833,6 +833,81 @@ func (z nat) shiftRightDeprecated(x nat, n uint) nat { } +func (z nat) and(x, y nat) nat { + m := len(x) + n := len(y) + if m > n { + m = n + } + // m <= n + + z = z.make(m) + for i := 0; i < m; i++ { + z[i] = x[i] & y[i] + } + + return z.norm() +} + + +func (z nat) andNot(x, y nat) nat { + m := len(x) + n := len(y) + if n > m { + n = m + } + // m >= n + + z = z.make(m) + for i := 0; i < n; i++ { + z[i] = x[i] &^ y[i] + } + copy(z[n:m], x[n:m]) + + return z.norm() +} + + +func (z nat) or(x, y nat) nat { + m := len(x) + n := len(y) + s := x + if m < n { + n, m = m, n + s = y + } + // n >= m + + z = z.make(n) + for i := 0; i < m; i++ { + z[i] = x[i] | y[i] + } + copy(z[m:n], s[m:n]) + + return z.norm() +} + + +func (z nat) xor(x, y nat) nat { + m := len(x) + n := len(y) + s := x + if n < m { + n, m = m, n + s = y + } + // n >= m + + z = z.make(n) + for i := 0; i < m; i++ { + z[i] = x[i] ^ y[i] + } + copy(z[m:n], s[m:n]) + + return z.norm() +} + + // greaterThan returns true iff (x1<<_W + x2) > (y1<<_W + y2) func greaterThan(x1, x2, y1, y2 Word) bool { return x1 > y1 || x1 == y1 && x2 > y2 } diff --git a/src/pkg/big/nat_test.go b/src/pkg/big/nat_test.go index f9adf3dd4..f353822f0 100644..100755 --- a/src/pkg/big/nat_test.go +++ b/src/pkg/big/nat_test.go @@ -173,37 +173,37 @@ func BenchmarkMul(b *testing.B) { } -type strN struct { +type str struct { x nat b int s string } -var tabN = []strN{ - strN{nil, 10, "0"}, - strN{nat{1}, 10, "1"}, - strN{nat{10}, 10, "10"}, - strN{nat{1234567890}, 10, "1234567890"}, +var tab = []str{ + str{nil, 10, "0"}, + str{nat{1}, 10, "1"}, + str{nat{10}, 10, "10"}, + str{nat{1234567890}, 10, "1234567890"}, } func TestString(t *testing.T) { - for _, a := range tabN { + for _, a := range tab { s := a.x.string(a.b) if s != a.s { - t.Errorf("stringN%+v\n\tgot s = %s; want %s", a, s, a.s) + t.Errorf("string%+v\n\tgot s = %s; want %s", a, s, a.s) } x, b, n := nat(nil).scan(a.s, a.b) if x.cmp(a.x) != 0 { - t.Errorf("scanN%+v\n\tgot z = %v; want %v", a, x, a.x) + t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x) } if b != a.b { - t.Errorf("scanN%+v\n\tgot b = %d; want %d", a, b, a.b) + t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.b) } if n != len(a.s) { - t.Errorf("scanN%+v\n\tgot n = %d; want %d", a, n, len(a.s)) + t.Errorf("scan%+v\n\tgot n = %d; want %d", a, n, len(a.s)) } } } |