Merge pull request #208 from whisk/master

lemire · web-flow · commit 996a67e02011 · 2025-10-12T15:07:43.000-04:00
fix off by 1 error in ShiftRight
diff --git a/bitset.go b/bitset.go
@@ -1531,7 +1531,7 @@ func (b *BitSet) ShiftRight(bits uint) {
 		return
 	}
 
-	if bits >= top {
+	if bits > top {
 		b.set = make([]uint64, wordsNeeded(b.length))
 		return
 	}
diff --git a/bitset_test.go b/bitset_test.go
@@ -2409,7 +2409,7 @@ func TestShiftRight(t *testing.T) {
 
 			count := 0
 			for _, i := range data {
-				if i > bits {
+				if i >= bits {
 					count++
 
 					if !b.Test(i - bits) {
@@ -2419,7 +2419,7 @@ func TestShiftRight(t *testing.T) {
 			}
 
 			if int(b.Count()) != count {
-				t.Error("bad bits count")
+				t.Errorf("bad bits count: expected %d, got %d", count, b.Count())
 			}
 		})
 	}
@@ -2434,6 +2434,43 @@ func TestShiftRight(t *testing.T) {
 	test("remove all", 242)
 }
 
+func TestShiftRightFull(t *testing.T) {
+	testCases := []struct{
+		data []uint
+		shiftDistance uint
+	}{
+		{
+			[]uint{20}, 20,
+		},
+		{
+			[]uint{0, 20, 40, 1260, 1280}, 1,
+		},
+		{
+			[]uint{0, 20, 40, 1260, 1280}, 1281,
+		},
+	}
+
+	test := func(data []uint, shiftDistance uint) {
+		b := New(0)
+		for i := range data {
+			b.Set(data[i])
+		}
+		b.ShiftRight(shiftDistance)
+		for i := range data {
+			shiftedBit := int(data[i])-int(shiftDistance)
+			if shiftedBit >= 0 {
+				if !b.Test(uint(shiftedBit)) {
+					t.Errorf("bit %d should be set after ShiftRight(%d) if bit %d was set prior", data[i]-shiftDistance, shiftDistance, data[i])
+				}
+			}
+		}
+	}
+
+	for i := range testCases {
+		test(testCases[i].data, testCases[i].shiftDistance)
+	}
+}
+
 func TestWord(t *testing.T) {
 	data := []uint64{0x0bfd85fc01af96dd, 0x3fe212a7eae11414, 0x7aa412221245dee1, 0x557092c1711306d5}
 	testCases := map[string]struct {

Original file line number	Diff line number	Diff line change
`@@ -1531,7 +1531,7 @@ func (b *BitSet) ShiftRight(bits uint) {`
`1531`	`1531`	`return`
`1532`	`1532`	`}`
`1533`	`1533`
`1534`		`- if bits >= top {`
	`1534`	`+ if bits > top {`
`1535`	`1535`	`b.set = make([]uint64, wordsNeeded(b.length))`
`1536`	`1536`	`return`
`1537`	`1537`	`}`