# Count numbers less than N whose Bitwise AND with N is zero

Given a positive integer **N**, the task is to count all numbers which are less than** N** and Bitwise AND of all such numbers with** N **is zero.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 5Output:2Explanation:

The integers less than N(= 5) whose Bitwise AND with 5 is 0 are 0 and 2. Hence, the total count is 2.

Input:N = 9Output:4

**Approach:** The given problem can be solved based on the observation that all bits which are set in **N** will be unset in any number which has Bitwise AND with **N** equal to **0**. Follow the steps below to solve the problem:

- Initialize a variable, say
**unsetBits**, equal to the total number of unset bits in the given integer**N**. - Now, every unset bit in
**N**can have either**0**or**1**in the corresponding position, as the Bitwise AND for any position where**N**has an unset bit will always be equal to**0**. Hence, the total number of different possibilities will be**2**raised to the power of**unsetBits**. - Therefore, print the value of 2 to the power of
**unsetBits**as the result.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count number of` `// unset bits in the integer N` `int` `countUnsetBits(` `int` `N)` `{` ` ` `// Stores the number of unset` ` ` `// bits in N` ` ` `int` `c = 0;` ` ` `while` `(N) {` ` ` `// Check if N is even` ` ` `if` `(N % 2 == 0) {` ` ` `// Increment the value of c` ` ` `c += 1;` ` ` `}` ` ` `// Right shift N by 1` ` ` `N = N >> 1;` ` ` `}` ` ` `// Return the value of` ` ` `// count of unset bits` ` ` `return` `c;` `}` `// Function to count numbers whose` `// Bitwise AND with N equal to 0` `void` `countBitwiseZero(` `int` `N)` `{` ` ` `// Stores the number` ` ` `// of unset bits in N` ` ` `int` `unsetBits = countUnsetBits(N);` ` ` `// Print the value of 2 to the` ` ` `// power of unsetBits` ` ` `cout << (1 << unsetBits);` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 9;` ` ` `countBitwiseZero(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG{` `// Function to count number of` `// unset bits in the integer N` `static` `int` `countUnsetBits(` `int` `N)` `{` ` ` `// Stores the number of unset` ` ` `// bits in N` ` ` `int` `c = ` `0` `;` ` ` `while` `(N != ` `0` `) {` ` ` `// Check if N is even` ` ` `if` `(N % ` `2` `== ` `0` `) {` ` ` `// Increment the value of c` ` ` `c += ` `1` `;` ` ` `}` ` ` `// Right shift N by 1` ` ` `N = N >> ` `1` `;` ` ` `}` ` ` `// Return the value of` ` ` `// count of unset bits` ` ` `return` `c;` `}` `// Function to count numbers whose` `// Bitwise AND with N equal to 0` `static` `void` `countBitwiseZero(` `int` `N)` `{` ` ` `// Stores the number` ` ` `// of unset bits in N` ` ` `int` `unsetBits = countUnsetBits(N);` ` ` `// Print the value of 2 to the` ` ` `// power of unsetBits` ` ` `System.out.print(` `1` `<< unsetBits);` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `9` `;` ` ` `countBitwiseZero(N);` `}` `}` `// This code is contributed by sanjoy_62.` |

## Python3

`# Python program for the above approach` `# Function to count number of` `# unset bits in the integer N` `def` `countUnsetBits(N):` ` ` ` ` `# Stores the number of unset` ` ` `# bits in N` ` ` `c ` `=` `0` ` ` `while` `(N):` ` ` `# Check if N is even` ` ` `if` `(N ` `%` `2` `=` `=` `0` `):` ` ` ` ` `# Increment the value of c` ` ` `c ` `+` `=` `1` ` ` ` ` `# Right shift N by 1` ` ` `N ` `=` `N >> ` `1` ` ` `# Return the value of` ` ` `# count of unset bits` ` ` `return` `c` `# Function to count numbers whose` `# Bitwise AND with N equal to 0` `def` `countBitwiseZero(N):` ` ` ` ` `# Stores the number` ` ` `# of unset bits in N` ` ` `unsetBits ` `=` `countUnsetBits(N)` ` ` `# Print value of 2 to the` ` ` `# power of unsetBits` ` ` `print` `((` `1` `<< unsetBits))` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `9` ` ` `countBitwiseZero(N)` ` ` `# This code is contributed by mohit kumar 29.` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `// Function to count number of` `// unset bits in the integer N` `static` `int` `countUnsetBits(` `int` `N)` `{` ` ` ` ` `// Stores the number of unset` ` ` `// bits in N` ` ` `int` `c = 0;` ` ` `while` `(N != 0) ` ` ` `{` ` ` ` ` `// Check if N is even` ` ` `if` `(N % 2 == 0)` ` ` `{` ` ` ` ` `// Increment the value of c` ` ` `c += 1;` ` ` `}` ` ` `// Right shift N by 1` ` ` `N = N >> 1;` ` ` `}` ` ` `// Return the value of` ` ` `// count of unset bits` ` ` `return` `c;` `}` `// Function to count numbers whose` `// Bitwise AND with N equal to 0` `static` `void` `countBitwiseZero(` `int` `N)` `{` ` ` ` ` `// Stores the number` ` ` `// of unset bits in N` ` ` `int` `unsetBits = countUnsetBits(N);` ` ` `// Print the value of 2 to the` ` ` `// power of unsetBits` ` ` `Console.Write(1 << unsetBits);` `}` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `N = 9;` ` ` ` ` `countBitwiseZero(N);` `}` `}` `// This code is contributed by shivanisinghss2110` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to count number of` `// unset bits in the integer N` `function` `countUnsetBits( N)` `{` ` ` `// Stores the number of unset` ` ` `// bits in N` ` ` `let c = 0;` ` ` `while` `(N != 0) {` ` ` `// Check if N is even` ` ` `if` `(N % 2 == 0) {` ` ` `// Increment the value of c` ` ` `c += 1;` ` ` `}` ` ` `// Right shift N by 1` ` ` `N = N >> 1;` ` ` `}` ` ` `// Return the value of` ` ` `// count of unset bits` ` ` `return` `c;` `}` `// Function to count numbers whose` `// Bitwise AND with N equal to 0` `function` `countBitwiseZero( N)` `{` ` ` `// Stores the number` ` ` `// of unset bits in N` ` ` `let unsetBits = countUnsetBits(N);` ` ` `// Print the value of 2 to the` ` ` `// power of unsetBits` ` ` `document.write(1 << unsetBits);` `}` `// Driver Code` ` ` `let N = 9;` ` ` `countBitwiseZero(N);` `// This code is contributed by shivansinghss2110` `</script>` |

**Output:**

4

**Time Complexity:** O(log N)**Auxiliary Space:** O(1)