Categories
28°C, New York
Home Data Structures and Algorithms Compute XOR from 1 to n (direct method)

Compute XOR from 1 to n (direct method)

2. Count of numbers (x) smaller than or equal to n such that n+x = n^x:

The  problem can be solved based on the following observations:

Say x = n%4. The XOR value depends on the value if x. If

  • x = 0, then the answer is n.
  • x = 1, then answer is 1.
  • x = 2, then answer is n+1.
  • x = 3, then answer is 0.

Below is the implementation of the above approach.

CPP 
// Direct XOR of all numbers from 1 to n
int computeXOR(int n)
{
    if (n % 4 == 0)
        return n;
    if (n % 4 == 1)
        return 1;
    if (n % 4 == 2)
        return n + 1;
    else
        return 0;
}
Java 
/*package whatever //do not write package name here */
import java.io.*;

class GFG
{
  
  // Direct XOR of all numbers from 1 to n
  public static int computeXOR(int n)
  {
    if (n % 4 == 0)
      return n;
    if (n % 4 == 1)
      return 1;
    if (n % 4 == 2)
      return n + 1;
    else
      return 0;
  }

  public static void main (String[] args) {

  }
}

// This code is contributed by akashish__
Python 
# Direct XOR of all numbers from 1 to n
def computeXOR(n):
    if (n % 4 is 0):
        return n
    if (n % 4 is 1):
        return 1
    if (n % 4 is 2):
        return n + 1
    else:
        return 0

      
# This code is contributed by akashish__
C# 
using System;
public class GFG
{

  // Direct XOR of all numbers from 1 to n
  public static int computeXOR(int n)
  {

    if (n % 4 == 0)

      return n;

    if (n % 4 == 1)

      return 1;

    if (n % 4 == 2)

      return n + 1;

    else

      return 0;

  }
  public static void Main(){}


}

// This code is contributed by akashish__
Javascript 
<script>

// Direct XOR of all numbers from 1 to n
function computeXOR(n)
{
    if (n % 4 == 0)
        return n;
    if (n % 4 == 1)
        return 1;
    if (n % 4 == 2)
        return n + 1;
    else
        return 0;
}

// This code is contributed by Shubham Singh

</script>

Time Complexity: O(1)
Auxiliary Space: O(1)

Refer Compute XOR from 1 to n for details.

Bits manipulation (Important tactics)

Prerequisites: Bitwise operators in C, Bitwise Hacks for Competitive Programming, Bit Tricks for Competitive Programming

Table of Contents

  • Compute XOR from 1 to n (direct method)
  • Count of numbers (x) smaller than or equal to n such that n+x = n^x
  • How to know if a number is a power of 2?
  • Find XOR of all subsets of a set
  • Find the number of leading, trailing zeroes and number of 1’s
  • Convert binary code directly into an integer in C++
  • The Quickest way to swap two numbers
  • Simple approach to flip the bits of a number
  • Finding the most significant set bit (MSB)
  • Check if a number has bits in an alternate pattern

Similar Reads

1. Compute XOR from 1 to n (direct method):

The  problem can be solved based on the following observations:...

2. Count of numbers (x) smaller than or equal to n such that n+x = n^x:

The count of such numbers x can be counted using the following mathematical trick....

3. How to know if a number is a power of 2?

This can be solved based on the following fact:...

4. Find XOR of all subsets of a set

We can do it in O(1) time. The answer is always 0 if the given set has more than one element. For sets with a single element, the answer is the value of the single element....

5. Find the number of leading, trailing zeroes and number of 1’s

We can quickly find the number of leading, trailing zeroes and number of 1’s in a binary code of an integer in C++ using GCC....

6. Convert binary code directly into an integer in C++

CPP // Conversion into Binary code #include using namespace std; int main() { auto number = 0b011; cout << number; return 0; } Java /*package whatever //do not write package name here */ // Conversion into Binary code import java.io.*; class GFG { public static void main(String[] args) { int number = 0b011; System.out.println(number); } } // This code is contributed by akashish__ Python # Python Code number = 0b011 print(number) # This code is contributed by akashish__ C# // Conversion into Binary code using System; public class GFG { static public void Main() { // Code int number = 0b011; Console.WriteLine(number); } } // This code is contributed by karthik Javascript // Conversion into Binary code let number = 0b011; console.log(number);...

7. The Quickest way to swap two numbers:

Two numbers can be swapped easily using the following bitwise operations:...

8. Finding the most significant set bit (MSB):

We can find the most significant set bit in O(1) time for a fixed size integer. For example below code is for 32-bit integer....

9. Check if a number has bits in an alternate pattern

We can quickly check if bits in a number are in an alternate pattern (like 101010)....

Tags:
#Bit Magic #Competitive Programming #DSA #Bit Magic

2. Count of numbers (x) smaller than or equal to n such that n+x = n^x: