diff --git a/.travis.yml b/.travis.yml
new file mode 100644
index 0000000..7d82325
--- /dev/null
+++ b/.travis.yml
@@ -0,0 +1,7 @@
+language: java
+sudo: false
+cache:
+  directories:
+    - $HOME/.m2/repository
+jdk:
+  - openjdk7
diff --git a/README.md b/README.md
index 484b687..2a8adb4 100644
--- a/README.md
+++ b/README.md
@@ -1,3 +1,8 @@
+[![][Build Status img]][Build Status]
+[![][license img]][license]
+[![][Maven Central img]][Maven Central]
+[![][Javadocs img]][Javadocs]
+
 SparseBitSet
 ============
 
@@ -18,7 +23,7 @@ presentation.  I can take credit for neither.
 <dependency>
    <groupId>com.zaxxer</groupId>
    <artifactId>SparseBitSet</artifactId>
-   <version>1.0</version>
+   <version>1.1</version>
    <scope>compile</scope>
 </dependency>
 ```
@@ -39,3 +44,15 @@ Using a custom hash table, where the key is an int = bitvalue / 64, and the valu
 Using a virtual-memory like structure, the SparseBitSet overhead is ~0.03 32-bit words overhead per 64 bits.
 
 For a full analysis, read Dr. Haddon's [slide stack](https://github.com/brettwooldridge/SparseBitSet/blob/master/SparseBitSet.pdf).
+
+[Build Status]:https://travis-ci.org/brettwooldridge/SparseBitSet
+[Build Status img]:https://travis-ci.org/brettwooldridge/SparseBitSet.svg?branch=master
+
+[license]:LICENSE
+[license img]:https://img.shields.io/badge/license-Apache%202-blue.svg
+   
+[Maven Central]:https://maven-badges.herokuapp.com/maven-central/com.zaxxer/SparseBitSet
+[Maven Central img]:https://maven-badges.herokuapp.com/maven-central/com.zaxxer/SparseBitSet/badge.svg
+   
+[Javadocs]:http://javadoc.io/doc/com.zaxxer/SparseBitSet
+[Javadocs img]:http://javadoc.io/badge/com.zaxxer/SparseBitSet.svg
diff --git a/pom.xml b/pom.xml
index 8159bd8..c3a259a 100644
--- a/pom.xml
+++ b/pom.xml
@@ -3,7 +3,7 @@
 
    <groupId>com.zaxxer</groupId>
    <artifactId>SparseBitSet</artifactId>
-   <version>1.1</version>
+   <version>1.2</version>
    <packaging>jar</packaging>
 
    <name>SparseBitSet</name>
@@ -50,7 +50,7 @@
       <dependency>
          <groupId>junit</groupId>
          <artifactId>junit</artifactId>
-         <version>3.8.1</version>
+         <version>4.12</version>
          <scope>test</scope>
       </dependency>
    </dependencies>
diff --git a/src/main/java/com/zaxxer/sparsebits/SparseBitSet.java b/src/main/java/com/zaxxer/sparsebits/SparseBitSet.java
index 9c266cd..81e31eb 100644
--- a/src/main/java/com/zaxxer/sparsebits/SparseBitSet.java
+++ b/src/main/java/com/zaxxer/sparsebits/SparseBitSet.java
@@ -12,7 +12,7 @@ import java.io.Serializable;
 /**
  *  This class implements a set of bits that grows as needed. Each bit of the
  *  bit set represents a <code>boolean</code> value. The values of a
- *  <code>SparseBitSet</code> are indexed by nonnegative integers.
+ *  <code>SparseBitSet</code> are indexed by non-negative integers.
  *  Individual indexed values may be examined, set, cleared, or modified by
  *  logical operations. One <code>SparseBitSet</code> or logical value may be
  *  used to modify the contents of (another) <code>SparseBitSet</code> through
@@ -31,9 +31,9 @@ import java.io.Serializable;
  *  <code>SparseBitSet</code> are labelled <code>
  *  0</code>&nbsp;..&nbsp;<code>Integer.MAX_VALUE&nbsp;&minus;&nbsp;1</code>.
  *  After the last set bit of a <code>SparseBitSet</code>, any attempt to find
- *  a subsequent bit (<i>getNextSetBit</i>()), will return an value of &minus;1.
- *  If an attempt is made to use <i>getNextClearBit</i>(), and all the bits are
- *  set from the starting postion of the search to the bit labelled
+ *  a subsequent bit (<i>nextSetBit</i>()), will return an value of &minus;1.
+ *  If an attempt is made to use <i>nextClearBit</i>(), and all the bits are
+ *  set from the starting position of the search to the bit labelled
  *  <code>Integer.MAX_VALUE&nbsp;&minus;&nbsp;1</code>, then similarly &minus;1
  *  will be returned.
  *  <p>
@@ -41,7 +41,7 @@ import java.io.Serializable;
  *  a <code>SparseBitSet</code> will result in a
  *  <code>NullPointerException</code>.
  *  <p>
- *  A <code>SparseBitSet</code> is not safe for multithreaded use without
+ *  A <code>SparseBitSet</code> is not safe for multi-threaded use without
  *  external synchronization.
  *
  * @author      Bruce K. Haddon
@@ -592,7 +592,7 @@ public class SparseBitSet implements Cloneable, Serializable
         setScanner(i, j, null, clearStrategy);
     }
 
-    /** 
+    /**
      *  Sets all of the bits in this <code>SparseBitSet</code> to
      *  <code>false</code>.
      *
@@ -651,8 +651,8 @@ public class SparseBitSet implements Cloneable, Serializable
 
     /**
      *  Compares this object against the specified object. The result is
-     *  <code>true</code> if and only if the argument is not <code>null</code> 
-     *  and is a <code>SparseBitSet</code> object that has exactly the same bits 
+     *  <code>true</code> if and only if the argument is not <code>null</code>
+     *  and is a <code>SparseBitSet</code> object that has exactly the same bits
      *  set to <code>true</code> as this bit set. That is, for every nonnegative
      *  <code>i</code> indexing a bit in the set,
      *  <pre>((SparseBitSet)obj).get(i) == this.get(i)</pre>
@@ -1011,6 +1011,150 @@ public class SparseBitSet implements Cloneable, Serializable
                         + Long.numberOfTrailingZeros(word));
     }
 
+    /**
+     * Returns the index of the nearest bit that is set to {@code false}
+     * that occurs on or before the specified starting index.
+     * If no such bit exists, or if {@code -1} is given as the
+     * starting index, then {@code -1} is returned.
+     *
+     * @param  i the index to start checking from (inclusive)
+     * @return the index of the previous clear bit, or {@code -1} if there
+     *         is no such bit
+     * @throws IndexOutOfBoundsException if the specified index is less
+     *         than {@code -1}
+     * @since  1.2
+     * @see java.util.BitSet#previousClearBit
+     */
+    public int previousClearBit(int i)
+    {
+        if (i < 0)
+        {
+            if (i == -1)
+                return -1;
+            throw new IndexOutOfBoundsException("i=" + i);
+        }
+
+        final long[][][] bits = this.bits;
+        final int aLength = bits.length;
+
+        int w = i >> SHIFT3;
+        int w3 = w & MASK3;
+        int w2 = (w >> SHIFT2) & MASK2;
+        int w1 = w >> SHIFT1;
+        if (w1 > aLength - 1)
+            return i;
+        w1 = Math.min(w1, aLength - 1);
+        final int w4 = i % LENGTH4;
+
+        long word;
+        long[][] a2;
+        long[] a3;
+
+        final int f3 = w3;
+        final int f2 = w2;
+        final int f1 = w1;
+
+        for (; w1 >= 0; --w1)
+        {
+            if ((a2 = bits[w1]) == null)
+                return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3)
+                        + (f1 == w1 ? w4 : LENGTH4 - 1);
+            for (; w2 >= 0; --w2)
+            {
+                if ((a3 = a2[w2]) == null)
+                    return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3)
+                            + (f2 == w2 ? w4 : LENGTH4 - 1);
+                for (; w3 >= 0; --w3)
+                {
+                    if ((word = a3[w3]) == 0)
+                        return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3)
+                                + (f3 == w3 ? w4 : LENGTH4 - 1);
+                    for (int bitIdx = w4; bitIdx >= 0; --bitIdx)
+                    {
+                        if ((word & (1L << bitIdx)) == 0)
+                            return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) + bitIdx;
+                    }
+                }
+                w3 = LENGTH3 - 1;
+            }
+            w2 = LENGTH2 - 1;
+            w3 = LENGTH3 - 1;
+        }
+        return -1;
+    }
+
+    /**
+     * Returns the index of the nearest bit that is set to {@code true}
+     * that occurs on or before the specified starting index.
+     * If no such bit exists, or if {@code -1} is given as the
+     * starting index, then {@code -1} is returned.
+     *
+     * @param  i the index to start checking from (inclusive)
+     * @return the index of the previous set bit, or {@code -1} if there
+     *         is no such bit
+     * @throws IndexOutOfBoundsException if the specified index is less
+     *         than {@code -1}
+     * @since  1.2
+     * @see java.util.BitSet#previousSetBit
+     */
+    public int previousSetBit(int i)
+    {
+        if (i < 0)
+        {
+            if (i == -1)
+                return -1;
+            throw new IndexOutOfBoundsException("i=" + i);
+        }
+
+        final long[][][] bits = this.bits;
+        final int aLength = bits.length;
+
+        /*  This is the word from which the search begins. */
+        final int w = i >> SHIFT3;
+        int w1 = w >> SHIFT1;
+        int w2, w3, w4;
+        /*  But if its off the end of the array, start from the very end. */
+        if (w1 > aLength - 1)
+        {
+            w1 = aLength - 1;
+            w2 = LENGTH2 - 1;
+            w3 = LENGTH3 - 1;
+            w4 = LENGTH4 - 1;
+        }
+        else
+        {
+            w2 = (w >> SHIFT2) & MASK2;
+            w3 = w & MASK3;
+            w4 = i % LENGTH4;
+        }
+        boolean initialWord = true;
+
+        long word;
+        long[][] a2;
+        long[] a3;
+        for (; w1 >= 0; --w1, initialWord = false)
+        {
+            if ((a2 = bits[w1]) != null)
+                for (; w2 >= 0; --w2, initialWord = false)
+                {
+                    if ((a3 = a2[w2]) != null)
+                        for (; w3 >= 0; --w3, initialWord = false)
+                        {
+                            if ((word = a3[w3]) != 0)
+                                for (int bitIdx = (initialWord ? w4 : LENGTH4 - 1); bitIdx >= 0; --bitIdx)
+                                {
+                                    if ((word & (1L << bitIdx)) != 0)
+                                        return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) + bitIdx;
+                                }
+                        }
+                    w3 = LENGTH3 - 1;
+                }
+            w2 = LENGTH2 - 1;
+            w3 = LENGTH3 - 1;
+        }
+        return -1;
+    }
+
     /**
      *  Performs a logical <b>OR</b> of the addressed target bit with the
      *  argument value. This bit set is modified so that the addressed bit has the
@@ -1352,7 +1496,7 @@ public class SparseBitSet implements Cloneable, Serializable
     /** Sequences of set bits longer than this value are shown by
      *  {@link #toString()} as a "sub-sequence," in the form <code>a..b</code>.
      *  Setting this value to zero causes each set bit to be listed individually.
-     *  The default default value is 2 (which means sequences of three or more 
+     *  The default default value is 2 (which means sequences of three or more
      *  bits set are shown as a subsequence, and all other set bits are listed
      *  individually).
      *  <p>
@@ -1570,7 +1714,7 @@ public class SparseBitSet implements Cloneable, Serializable
             newSize = MAX_LENGTH1;
         final int aLength1 = (bits != null ? bits.length : 0);
 
-        if (newSize != aLength1)
+        if (newSize != aLength1 || bits == null)
         { // only if the size needs to be changed
             final long[][][] temp = new long[newSize][][]; //  Get the new array
             if (aLength1 != 0)
@@ -1839,7 +1983,7 @@ public class SparseBitSet implements Cloneable, Serializable
     //==============================================================================
 
     /**
-     *  Save the state of the <code>SparseBitSet</code> instance to a stream 
+     *  Save the state of the <code>SparseBitSet</code> instance to a stream
      *  (<i>i.e.</i>, serialize it).
      *
      * @param       s the ObjectOutputStream to which to write the serialized object
@@ -1848,7 +1992,7 @@ public class SparseBitSet implements Cloneable, Serializable
      *              inconsistent
      *
      * @serialData  The default data is emitted, followed by the current
-     *              <i>compactionCount</i> for the bit set, and then the 
+     *              <i>compactionCount</i> for the bit set, and then the
      *              <i>length</i> of the set (the position of the last bit),
      *              followed by the <i>cache.count</i> value (an <code>int</code>,
      *              the number of <code>int-&gt;long</code> pairs needed to describe
@@ -1902,7 +2046,7 @@ public class SparseBitSet implements Cloneable, Serializable
     private static final long serialVersionUID = -6663013367427929992L;
 
     /**
-     *  Reconstitute the <code>SparseBitSet</code> instance from a stream 
+     *  Reconstitute the <code>SparseBitSet</code> instance from a stream
      *  (<i>i.e.</i>, deserialize it).
      *
      * @param       s the ObjectInputStream to use
diff --git a/src/test/java/com/zaxxer/sparsebits/InitWithZeroTest.java b/src/test/java/com/zaxxer/sparsebits/InitWithZeroTest.java
new file mode 100644
index 0000000..cc4b71c
--- /dev/null
+++ b/src/test/java/com/zaxxer/sparsebits/InitWithZeroTest.java
@@ -0,0 +1,44 @@
+package com.zaxxer.sparsebits;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+public class InitWithZeroTest {
+    private SparseBitSet bitset;
+
+    @Before
+    public void setup() {
+        bitset = new SparseBitSet(0);
+    }
+
+    @Test
+    public void testPreviousSetBit() {
+        Assert.assertEquals(-1, bitset.previousSetBit(0));
+    }
+
+    @Test
+    public void testPreviousClearBit() {
+        Assert.assertEquals(0, bitset.previousClearBit(0));
+    }
+
+    @Test
+    public void testNextSetBit() {
+        Assert.assertEquals(-1, bitset.nextSetBit(0));
+    }
+
+    @Test
+    public void testNextClearBit() {
+        Assert.assertEquals(0, bitset.nextClearBit(0));
+    }
+
+    @Test
+    public void testClone() {
+        Assert.assertEquals(-1, bitset.clone().nextSetBit(0));
+    }
+
+    @Test
+    public void testAnd() {
+        bitset.and(new SparseBitSet());
+    }
+}
diff --git a/src/test/java/com/zaxxer/sparsebits/PreviousClearBitTest.java b/src/test/java/com/zaxxer/sparsebits/PreviousClearBitTest.java
new file mode 100644
index 0000000..730dbcc
--- /dev/null
+++ b/src/test/java/com/zaxxer/sparsebits/PreviousClearBitTest.java
@@ -0,0 +1,209 @@
+package com.zaxxer.sparsebits;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+import java.util.HashSet;
+import java.util.Random;
+import java.util.Set;
+
+import static com.zaxxer.sparsebits.SparseBitSet.SHIFT1;
+import static com.zaxxer.sparsebits.SparseBitSet.SHIFT2;
+import static com.zaxxer.sparsebits.SparseBitSet.SHIFT3;
+
+/**
+ * @author <a href="mailto:brent.n.douglas@gmail.com">Brent Douglas</a>
+ */
+public class PreviousClearBitTest extends Assert {
+
+    SparseBitSet set;
+
+    @Before
+    public void setUp() {
+        set = new SparseBitSet();
+    }
+
+    @Test
+    public void minusOne() throws Exception {
+        final int ret = set.previousClearBit(-1);
+
+        assertEquals(-1, ret);
+    }
+
+    @Test
+    public void emptySet() throws Exception {
+        final int ret = set.previousClearBit(0);
+
+        assertEquals(0, ret);
+    }
+
+    @Test
+    public void bottomBit() throws Exception {
+        final int ret = set.previousClearBit(1);
+
+        assertEquals(1, ret);
+    }
+
+    @Test
+    public void sameBit() throws Exception {
+        set.set(12345);
+        final int ret = set.previousClearBit(12345);
+
+        assertEquals(12344, ret);
+    }
+
+    @Test
+    public void level1Miss() throws Exception {
+        final int i = (1 << (SHIFT1 + SHIFT3));
+        set.set(i);
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level1MissPlus1() throws Exception {
+        final int i = (1 << (SHIFT1 + SHIFT3)) + 1;
+        set.set(i);
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level1MissMinus1() throws Exception {
+        final int i = (1 << (SHIFT1 + SHIFT3)) - 1;
+        set.set(i);
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level2Miss() throws Exception {
+        final int i = (1 << (SHIFT3 + SHIFT2));
+        set.set(i);
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level2MissPlus1() throws Exception {
+        final int i = (1 << (SHIFT3 + SHIFT2)) + 1;
+        set.set(i);
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level2MissMinus1() throws Exception {
+        final int i = (1 << (SHIFT3 + SHIFT2)) - 1;
+        set.set(i);
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level3Miss() throws Exception {
+        final int i = (1 << SHIFT3);
+        set.set(i);
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level3MissPlus1() throws Exception {
+        final int i = (1 << SHIFT3) + 1;
+        set.set(i);
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level3MissMinus1() throws Exception {
+        final int i = (1 << SHIFT3) - 1;
+        set.set(i);
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void noneBelow() throws Exception {
+        set.set(1);
+        final int ret = set.previousClearBit(1);
+
+        assertEquals(0, ret);
+    }
+
+    @Test
+    public void oneBelow() throws Exception {
+        set.set(1);
+        final int ret = set.previousClearBit(2);
+
+        assertEquals(2, ret);
+    }
+
+    @Test
+    public void threeNoSet() throws Exception {
+        set.set(1);
+        final int ret = set.previousClearBit(3);
+
+        assertEquals(3, ret);
+    }
+
+    @Test
+    public void threeSet() throws Exception {
+        set.set(3);
+        final int ret = set.previousClearBit(3);
+
+        assertEquals(2, ret);
+    }
+
+    @Test
+    public void topBit() throws Exception {
+        final int i = Integer.MAX_VALUE - 1;
+        final int ret = set.previousClearBit(i);
+
+        assertEquals(i, ret);
+    }
+
+    @Test
+    public void randomSingleEntry() throws Exception {
+        final Random random = new Random(0);
+        for (int i = 0; i < 10000; ++i) {
+            set = new SparseBitSet();
+            final int x = Math.abs(random.nextInt() + 1);
+            final int ret = set.previousClearBit(x);
+            assertEquals("Failed on i = " + i, x, ret);
+        }
+    }
+
+    @Test
+    public void randomMultiEntry() throws Exception {
+        final Random random = new Random(0);
+        final Set<Integer> values = new HashSet<Integer>();
+        for (int i = 0; i < 10000; ++i) {
+            set = new SparseBitSet();
+            for (int j = 0; j < 1000; ++j) {
+                final int x = Math.abs(random.nextInt() + 1);
+                set.set(x);
+                values.add(x);
+            }
+            final int x = Math.abs(random.nextInt() + 1);
+            int expected = x;
+            while (values.contains(expected)) {
+                --expected;
+            }
+            final int ret = set.previousClearBit(x);
+            assertEquals("Failed on i = " + i + " x = " + x, expected, ret);
+            values.clear();
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/test/java/com/zaxxer/sparsebits/PreviousSetBitTest.java b/src/test/java/com/zaxxer/sparsebits/PreviousSetBitTest.java
new file mode 100644
index 0000000..488518b
--- /dev/null
+++ b/src/test/java/com/zaxxer/sparsebits/PreviousSetBitTest.java
@@ -0,0 +1,233 @@
+package com.zaxxer.sparsebits;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Random;
+
+import static com.zaxxer.sparsebits.SparseBitSet.SHIFT1;
+import static com.zaxxer.sparsebits.SparseBitSet.SHIFT2;
+import static com.zaxxer.sparsebits.SparseBitSet.SHIFT3;
+
+/**
+ * @author <a href="mailto:brent.n.douglas@gmail.com">Brent Douglas</a>
+ */
+public class PreviousSetBitTest extends Assert {
+
+    SparseBitSet set;
+
+    @Before
+    public void setUp() {
+        set = new SparseBitSet();
+    }
+
+    @Test
+    public void emptySet() throws Exception {
+        final int ret = set.previousSetBit(0);
+
+        assertEquals(-1, ret);
+    }
+
+    @Test
+    public void bottomBit() throws Exception {
+        set.set(0);
+        final int ret = set.previousSetBit(0);
+
+        assertEquals(0, ret);
+    }
+
+    @Test
+    public void betweenTwo() throws Exception {
+        set.set(4);
+        set.set(8);
+        final int ret = set.previousSetBit(5);
+
+        assertEquals(4, ret);
+    }
+
+    @Test
+    public void inRun() throws Exception {
+        set.set(4);
+        set.set(8);
+        set.set(13);
+        set.set(25);
+        set.set(268);
+        final int ret = set.previousSetBit(22);
+
+        assertEquals(13, ret);
+    }
+
+    @Test
+    public void sameBit() throws Exception {
+        set.set(12345);
+        final int ret = set.previousSetBit(12345);
+
+        assertEquals(12345, ret);
+    }
+
+    @Test
+    public void noneBelow() throws Exception {
+        set.set(1);
+        final int ret = set.previousSetBit(0);
+
+        assertEquals(-1, ret);
+    }
+
+    @Test
+    public void oneBelow() throws Exception {
+        set.set(1);
+        final int ret = set.previousSetBit(2);
+
+        assertEquals(1, ret);
+    }
+
+    @Test
+    public void twoBelow() throws Exception {
+        set.set(1);
+        final int ret = set.previousSetBit(3);
+
+        assertEquals(1, ret);
+    }
+
+    @Test
+    public void topBit() throws Exception {
+        final int i = Integer.MAX_VALUE - 1;
+        set.set(i);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i, ret);
+    }
+
+    @Test
+    public void level1Miss() throws Exception {
+        final int i = (1 << (SHIFT1 + SHIFT3));
+        set.set(i - 1);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level1MissPlus1() throws Exception {
+        final int i = (1 << (SHIFT1 + SHIFT3)) + 1;
+        set.set(i - 1);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level1MissMinus1() throws Exception {
+        final int i = (1 << (SHIFT1 + SHIFT3)) - 1;
+        set.set(i - 1);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level2Miss() throws Exception {
+        final int i = (1 << (SHIFT3 + SHIFT2));
+        set.set(i - 1);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level2MissPlus1() throws Exception {
+        final int i = (1 << (SHIFT3 + SHIFT2)) + 1;
+        set.set(i - 1);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level2MissMinus1() throws Exception {
+        final int i = (1 << (SHIFT3 + SHIFT2)) - 1;
+        set.set(i - 1);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level3Miss() throws Exception {
+        final int i = (1 << SHIFT3);
+        set.set(i - 1);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level3MissPlus1() throws Exception {
+        final int i = (1 << SHIFT3) + 1;
+        set.set(i - 1);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void level3MissMinus1() throws Exception {
+        final int i = (1 << SHIFT3) - 1;
+        set.set(i - 1);
+        final int ret = set.previousSetBit(i);
+
+        assertEquals(i - 1, ret);
+    }
+
+    @Test
+    public void randomSingleEntry() throws Exception {
+        final int max = Integer.MAX_VALUE - 1;
+        final Random random = new Random(0);
+        for (int i = 0; i < 10000; ++i) {
+            set = new SparseBitSet();
+            final int x = Math.abs(random.nextInt() + 1);
+            set.set(x);
+            final int ret = set.previousSetBit(max);
+            assertEquals("Failed on i = " + i, x, ret);
+        }
+    }
+
+    @Test
+    public void randomMultiEntry() throws Exception {
+        randomMultiEntry(Integer.MAX_VALUE);
+    }
+
+    @Test
+    public void randomMultiEntryTight() throws Exception {
+        randomMultiEntry(2000);
+    }
+
+    public void randomMultiEntry(final int max) throws Exception {
+        final Random random = new Random(0);
+        final List<Integer> values = new ArrayList<Integer>();
+        for (int i = 0; i < 10000; ++i) {
+            set = new SparseBitSet();
+            for (int j = 0; j < 1000; ++j) {
+                final int x = Math.abs(random.nextInt() + 1) % max;
+                set.set(x);
+                values.add(x);
+            }
+            final int x = Math.abs(random.nextInt() + 1) % max;
+            Collections.sort(values);
+            int expected = -1;
+            for (final Integer val : values) {
+                if (val > x) {
+                    break;
+                }
+                expected = val;
+            }
+            final int ret = set.previousSetBit(x);
+            assertEquals("Failed on i = " + i, expected, ret);
+            values.clear();
+        }
+    }
+}
\ No newline at end of file