hamming_weight_fun

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from scipy.special import comb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "SQUARES = set([0, 1, 4, 9, 16, 25, 36, 49, 64])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def hamming_weight(n):\n",
    "    return binary_representation(n).count(\"1\")\n",
    "\n",
    "def binary_representation(n):\n",
    "    return bin(n)[2:]\n",
    "\n",
    "def brute_force_get_filtered_hamming_count(bound, filter_set=None):\n",
    "    if not filter_set:\n",
    "        filter_set = set()\n",
    "    count = 0\n",
    "    for i in range(bound + 1):\n",
    "        if hamming_weight(i) in filter_set:          \n",
    "            count += 1\n",
    "        # window dressing \n",
    "        #print i, binary_representation(i), count\n",
    "    return count\n",
    "\n",
    "def get_filtered_hamming_count(bound, filter_set=None):\n",
    "    \"\"\"\n",
    "        A function which counts the numbers in the interval [0, @param bound] \n",
    "        whose hamming weight is in @param filter_set\n",
    "        \n",
    "        Complexity: O(log2(bound) * len(filter_set) * max(filter_set)) \n",
    "        -- assuming optimal time complexity for the implemntation of \n",
    "        comb(n, k) is O(k).\n",
    "    \"\"\"\n",
    "    if not filter_set:\n",
    "        return 0\n",
    "    \n",
    "    bits = binary_representation(bound)\n",
    "    bit_length = len(bits) # == floor(log2(bound)) + 1\n",
    "    \n",
    "    # Preprocess to get allowable_prefixes:\n",
    "    # We generate a set of prefixes such that the binary strings with those prefixes are contained in the interval [0, bound]\n",
    "    # and every number in [0, bound] has such a prefix in it's binary representation. \n",
    "    allowable_prefixes = set()\n",
    "    current_prefix = \"\"\n",
    "    for i in range(len(bits)):\n",
    "        if bits[i] == \"1\":\n",
    "            # In this case,  numbers which begin with current_prefix + \"0\" are less than bound (regardless of the values of the following bits),\n",
    "            # and do not begin with any other prefix that is in allowable_prefixes (by construction).\n",
    "            allowable_prefixes.add(current_prefix + \"0\")\n",
    "        current_prefix += bits[i]\n",
    "    allowable_prefixes.add(current_prefix)\n",
    "    \n",
    "    count = 0\n",
    "    for k in allowable_prefixes: \n",
    "        for s in filter_set:\n",
    "            count += int(comb(bit_length - len(k) , s - k.count(\"1\")))\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# random small test\n",
    "for i in range(1024 + 1):\n",
    "    us = get_filtered_hamming_count(i, SQUARES)\n",
    "    them = brute_force_get_filtered_hamming_count(i, SQUARES)\n",
    "    if us != them:\n",
    "        print us, them"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}