2. Counting Bits.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "afd8ae70",
   "metadata": {},
   "source": [
    "---\n",
    "---\n",
    "\n",
    "<center> <h1> Counting Bits Problem </h1> </center>\n",
    "\n",
    "---\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d7ee92f",
   "metadata": {},
   "source": [
    "## Problem Statement: Version 1\n",
    "\n",
    "Counting Bits is a  problem that involves counting the number of 1's in the binary representation of a given number.\n",
    "\n",
    "- Given a non-negative integer, write a function that returns the number of 1's in its binary representation.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e34fdfca",
   "metadata": {},
   "source": [
    "## Approach\n",
    "\n",
    "To solve this problem, we can use **bitwise operations**. We can isolate each bit of the number and check if it is a 1 or a 0. We can use the **bitwise AND operator (&)** to check if the rightmost bit is a 1 and if so, we increment a counter. Then we shift the number to the right by one bit and repeat the process until the number becomes zero.\n",
    "\n",
    "- **Sample Input:** 5\n",
    "- **Sample Output:** 2\n",
    "\n",
    "In this sample example, there is non-negative integer 5 given as input. And the binary representation of 5 is 101 so count of  1's in binary representation is 2. Hence, the output is 2.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97ed9633",
   "metadata": {},
   "source": [
    "## Use Cases\n",
    "\n",
    "The Counting Bits problem has several use cases in computer science and programming.\n",
    "\n",
    "- **1. Cryptography:** In cryptography, the \"Counting Bits\" problem can be used to count the number of 1's in the binary representation of a cryptographic key which can then be used to assess the strength of the key. By analyzing the distribution of 1's in the key, we can identify patterns and optimize the key generation process to improve the security of the system.\n",
    "\n",
    "- **2. Machine learning:** In machine learning, the \"Counting Bits\" problem can be used to count the number of 1's in the binary representation of features which can then be used to train models and make predictions. By analyzing the distribution of 1's in the features, we can also identify important features and optimize the model to improve its accuracy and performance.\n",
    "\n",
    "- **3. Image Processing & Computer Vision:** In image processing, images are often represented in binary form using pixels where each pixel is a small square or dot that contains a binary value representing the color and brightness of the pixel. In computer vision, we often need to extract features from images in order to perform tasks such as object detection, image recognition and classification. \n",
    "> The \"Counting Bits\" problem can be used to count the number of 1's in the binary representation of each pixel in an image. This information can then be used to extract features such as edge density, texture and contrast which are important for tasks such as image segmentation and object recognition. By analyzing the distribution of 1's in the binary representation of an image, we can also identify patterns and structures that may be relevant to the task at hand.\n",
    ". \n",
    "- **4. Genetics:** In genetics, DNA sequences are often represented using binary digits where each digit represents a nucleotide (A, C, G, or T). The \"Counting Bits\" problem can be used to count the number of 1's in the binary representation of each DNA sequence which can then be used to identify patterns and variations in the genome.\n",
    "\n",
    "- **5. Hardware Design:** In hardware design, digital circuits are often represented using binary logic gates where each gate performs a logical operation on one or more binary inputs and produces a binary output. The \"Counting Bits\" problem can be used to count the number of 1's in the binary representation of the input and output signals of a gate which is useful for **optimizing the performance and power consumption of the circuit**.\n",
    "> By analyzing the distribution of 1's in the binary representation of the input and output signals, we can identify patterns and optimize the circuit design to reduce the number of logic gates and improve the circuit's performance. For example, we can use the \"Counting Bits\" problem to identify gates that perform similar logical operations and combine them into a single gate, or to identify gates that produce constant output values and remove them from the circuit altogether.\n",
    "\n",
    "- **6. Computer Architecture:** In computer architecture, \"Counting Bits\" problem is used in **cache optimization**. Caches are small, fast memory structures that store frequently accessed data to improve the performance of the computer system. The \"Counting Bits\" problem can be used to count the number of 1's in the binary representation of memory addresses which can then be used to optimize the cache design and reduce the number of cache misses.\n",
    "> By analyzing the distribution of 1's in the binary representation of memory addresses, we can identify patterns and optimize the cache design to improve the hit rate and reduce the number of cache misses. For example, we can use the \"Counting Bits\" problem to identify frequently accessed memory blocks and store them in the cache, or to identify memory blocks that are rarely accessed and remove them from the cache to make room for more frequently accessed data.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed45afc9",
   "metadata": {},
   "source": [
    "## Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "id": "93a66b39",
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_bits(num):\n",
    "    \"\"\"\n",
    "    This function takes a non-negative integer as input and returns the number of 1's in \n",
    "    its binary representation.\n",
    "\n",
    "    Parameters:\n",
    "        num (int): A non-negative integer to count the number of 1's in its binary representation.\n",
    "\n",
    "    Returns:\n",
    "        int: The count of 1's in the binary representation of the input number.\n",
    "    \n",
    "    Example:\n",
    "        count_bits(5) -> 2\n",
    "        count_bits(8) -> 1\n",
    "        count_bits(15) -> 4\n",
    "    \"\"\"\n",
    "    count = 0\n",
    "    while num > 0:\n",
    "        if num & 1 == 1:\n",
    "            count +=1\n",
    "        num >>=1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29157b38",
   "metadata": {},
   "source": [
    "## Test Cases"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "id": "83652194",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_bits(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "id": "8b4d8267",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 175,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_bits(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "id": "b4c21234",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 176,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_bits(15)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c4a541f",
   "metadata": {},
   "source": [
    "## Explaination: Working of Function"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83a5a42e",
   "metadata": {},
   "source": [
    "- 1. The function count_bits takes a **non-negative integer num as input** and **initializes a count variable count to 0**.\n",
    "\n",
    "- 2. The function starts a **while loop** that runs **until num is equal to 0**. This ensures that all bits in the binary representation of num are processed.\n",
    "\n",
    "- 3. Inside the while loop, the function checks if the **rightmost bit of num** is equal to 1 by performing a **bitwise AND operation between num and 1**. If the result is 1, this means that the rightmost bit of num is 1 and the function **increments the count variable by 1**.\n",
    "\n",
    "- 4. After checking the rightmost bit of num, the function **right shifts the value of num by one position** using the **right shift operator (>>)**. This **removes the rightmost bit from the binary representation of num** and prepares the number for the **next iteration of the loop**.\n",
    "\n",
    "- 5. The loop continues to process the bits in the binary representation of num in the same manner **checking the rightmost bit, incrementing the count variable if the bit is equal to 1 and right shifting the value of num by one position**.\n",
    "\n",
    "Once all bits in the binary representation of num have been processed, the loop terminates and the function returns the **final value of the count variable** which **represents the number of 1's in the binary representation of the original input number num**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "id": "42f613da",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Step-1\n",
    "input_num = 15\n",
    "count_var = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "id": "48b6f63d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 178,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "id": "97bc5308",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 179,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_var"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "id": "4bf6aa6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step-2 While loop starts since input_num is not 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "id": "3cd80eb4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 181,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Step-3.1 Inside the while loop\n",
    "input_num & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "id": "bfc0c619",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 182,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_num & 1 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "id": "9375e361",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 183,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# # Step-3.2 Inside the while loop\n",
    "count_var +=1\n",
    "\n",
    "count_var"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "id": "bdc56284",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step-4 Inside the while loop\n",
    "input_num >>=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "id": "493b9e78",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 185,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Iteration-2 While loop\n",
    "input_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "id": "c3d7fd79",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 186,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Step-3.1 Inside the while loop\n",
    "input_num & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "id": "9f2d07e9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 187,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_num & 1 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "id": "5b4bdafc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 188,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Step-3.2 Inside the while loop\n",
    "count_var +=1\n",
    "\n",
    "count_var"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "id": "dabfb483",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step-4 Inside the while loop\n",
    "input_num >>=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "id": "5d329975",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 190,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Iteration-3 While loop\n",
    "input_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "id": "ef5f18f2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 191,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Step-3.1 Inside the while loop\n",
    "input_num & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "id": "101d3e1c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 192,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_num & 1 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "id": "ca42edf3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 193,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Step-3.2 Inside the while loop\n",
    "count_var +=1\n",
    "\n",
    "count_var"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "id": "c3f9872f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step-4 Inside the while loop\n",
    "input_num >>=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "id": "c60d0c0f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 195,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Iteration-4 While loop\n",
    "input_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "id": "397920c7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 196,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Step-3.1 Inside the while loop\n",
    "input_num & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "id": "d19dadac",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 197,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "input_num & 1 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "id": "fd5889ab",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 198,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Step-3.2 Inside the while loop\n",
    "count_var +=1\n",
    "\n",
    "count_var"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "id": "71ab82fc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Step-4 Inside the while loop\n",
    "input_num >>=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "id": "0fc68db3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 200,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# While loop stops since input_num is 0\n",
    "input_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "id": "f461309c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 201,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# final value of count_var\n",
    "count_var"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d7646f5",
   "metadata": {},
   "source": [
    "---\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "123435c3",
   "metadata": {},
   "source": [
    "## Problem Statement: Version 2\n",
    "\n",
    "Given a non-negative integer, write a function to return an array of length (length of the integer + 1) by counting the number of 1's in the binary representation of the index number of each element of the array. \n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cc7f4b7",
   "metadata": {},
   "source": [
    "## Approach\n",
    "\n",
    "To solve this problem,  return an array of the length n+1 where the elements will be the count of number of 1's present in the binary representation of the index number of each value in the array.\n",
    "\n",
    "- **Sample Input:** 5\n",
    "- **Sample Output:** [0,1,1,2,1,2]\n",
    "\n",
    "The output array contains the count of number of 1's in the binary representation of the index number of each element in the array. Index numbers and their binary representations when the input is **5 as\n",
    "[0:0, 1:1, 2:10, 3:11, 4:100, 5:101]**\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5976cb2c",
   "metadata": {},
   "source": [
    "## Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "id": "f10bf657",
   "metadata": {},
   "outputs": [],
   "source": [
    "def CountBits(num_i):\n",
    "    \"\"\"\n",
    "    Counts the number of 1 bits in the binary representation of each number in the \n",
    "    range from 0 to num.\n",
    "\n",
    "    Parameters:\n",
    "        num: An integer representing the upper bound of the range of numbers to be processed.\n",
    "\n",
    "    Returns:\n",
    "        A list of integers representing the number of 1 bits in the binary representation of \n",
    "        each number in the range from 0 to num. The i-th element of the list corresponds to \n",
    "        the i-th number in the range from 0 to num.\n",
    "    \"\"\"\n",
    "    bit_count_list = [0]\n",
    "    if num_i >= 1:\n",
    "        while len(bit_count_list) <= num_i:\n",
    "            bit_count_list_length = len(bit_count_list)\n",
    "            for index in range(bit_count_list_length):\n",
    "                bit_count_list.append(bit_count_list[index] + 1)\n",
    "        return bit_count_list[:num_i+1]\n",
    "    else:\n",
    "        return[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03bd8581",
   "metadata": {},
   "source": [
    "## Test Cases"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 203,
   "id": "2e9fbccb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 2, 1, 2]"
      ]
     },
     "execution_count": 203,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CountBits(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "id": "240aa95c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2]"
      ]
     },
     "execution_count": 204,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CountBits(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22567a8b",
   "metadata": {},
   "source": [
    "## Explanation: Working of Function"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9834efa",
   "metadata": {},
   "source": [
    "- Step 1: Initialize the counter list with a single element 0\n",
    "\n",
    "- Step 2: Check if the input number is greater than or equal to 1\n",
    "\n",
    "- Step 3: Enter a loop that continues until the length of counter is greater than num\n",
    "\n",
    "- Step 4: Get the current length of counter\n",
    "\n",
    "- Step 5: Loop through the existing elements of counter up to the current length\n",
    "\n",
    "- Step 6: Append a new element to the end of the list that is obtained by adding 1 to the corresponding element\n",
    "\n",
    "- Step 7: Return the counter list, but only up to the index corresponding to num+1, as the range of numbers is from 0 to num\n",
    "\n",
    "- Step 8: If num is less than 1, return a list with a single element 0"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}