public static void serializeHLL(OutputStream out, HyperLogLog hll) throws IOException {

    // write header
    out.write(MAGIC);
    int fourthByte = 0;
    int p = hll.getNumRegisterIndexBits();
    fourthByte = (p & 0xff) << 4;

    int bitWidth = 0;
    EncodingType enc = hll.getEncoding();

    // determine bit width for bitpacking and encode it in header
    if (enc.equals(EncodingType.DENSE)) {
      int lzr = hll.getHLLDenseRegister().getMaxRegisterValue();
      bitWidth = getBitWidth(lzr);

      // the max value of number of zeroes for 64 bit hash can be encoded using
      // only 6 bits. So we will disable bit packing for any values >6
      if (bitWidth > 6) {
        fourthByte |= 7;
        bitWidth = 8;
      } else {
        fourthByte |= (bitWidth & 7);
      }
    }

    // write fourth byte of header
    out.write(fourthByte);

    // write estimated count
    long estCount = hll.estimateNumDistinctValues();
    writeVulong(out, estCount);

    // serialize dense/sparse registers. Dense registers are bitpacked whereas
    // sparse registers are delta and variable length encoded
    if (enc.equals(EncodingType.DENSE)) {
      byte[] register = hll.getHLLDenseRegister().getRegister();
      bitpackHLLRegister(out, register, bitWidth);
    } else if (enc.equals(EncodingType.SPARSE)) {
      Map<Integer, Byte> sparseMap = hll.getHLLSparseRegister().getSparseMap();

      // write the number of elements in sparse map (required for
      // reconstruction)
      writeVulong(out, sparseMap.size());

      // compute deltas and write the values as varints
      int prev = 0;
      for (Map.Entry<Integer, Byte> entry : sparseMap.entrySet()) {
        if (prev == 0) {
          prev = (entry.getKey() << HLLConstants.Q_PRIME_VALUE) | entry.getValue();
          writeVulong(out, prev);
        } else {
          int curr = (entry.getKey() << HLLConstants.Q_PRIME_VALUE) | entry.getValue();
          int delta = curr - prev;
          writeVulong(out, delta);
          prev = curr;
        }
      }
    }
  }
HyperLogLog is serialized using the following format

<pre>
|-4 byte-|------varlong----|varint (optional)|----------|
---------------------------------------------------------
| header | estimated-count | register-length | register |
---------------------------------------------------------

<b>4 byte header</b> is encoded like below
3 bytes - HLL magic string to identify serialized stream
4 bits  - p (number of bits to be used as register index)
1       - spare bit (not used)
3 bits  - encoding (000 - sparse, 001..110 - n bit packing, 111 - no bit packing)

Followed by header are 3 fields that are required for reconstruction
of hyperloglog
Estimated count - variable length long to store last computed estimated count.
                  This is just for quick lookup without deserializing registers
Register length - number of entries in the register (required only for
                  for sparse representation. For bit-packing, the register
                  length can be found from p)
</pre>
@param out
         - output stream to write to
@param hll
         - hyperloglog that needs to be serialized
@throws IOException
standalone-metastore/metastore-server/src/main/java/org/apache/hadoop/hive/common/ndv/hll/HyperLogLogUtils.java