Table of Contents

Complete Bitwise Operator Reference

Java provides seven bitwise operators. They operate on the individual bits of int (32-bit) and long (64-bit) values. Every bit position is processed independently.

Binary Representations — Seeing the Bits

Use Integer.toBinaryString() to visualize what is happening at the bit level.

int a = 0b1010;  // 10 in decimal
int b = 0b1100;  // 12 in decimal

System.out.println(Integer.toBinaryString(a & b));  // 1000  (AND: both bits must be 1)
System.out.println(Integer.toBinaryString(a | b));  // 1110  (OR:  either bit is 1)
System.out.println(Integer.toBinaryString(a ^ b));  // 0110  (XOR: exactly one bit is 1)
System.out.println(Integer.toBinaryString(~a));     // 11111111111111111111111111110101

Notice that ~a flips all 32 bits, not just the significant ones. Since a = 0b00000000000000000000000000001010, the complement is 0b11111111111111111111111111110101, which is -11 in two's complement.

Shift Operators: >> vs >>>

This is one of the most commonly confused topics. Java has two right-shift operators:

• >> (arithmetic right shift): shifts bits right, filling the leftmost bits with the sign bit. Preserves the sign of negative numbers.
• >>> (logical right shift): shifts bits right, filling the leftmost bits with 0s. Always produces a non-negative result (for positive shift amounts).

int neg = -8;  // binary: 11111111111111111111111111111000

System.out.println(neg >> 2);   // -2   (sign preserved, fills with 1s)
// 11111111111111111111111111111110

System.out.println(neg >>> 2);  // 1073741822  (fills with 0s)
// 00111111111111111111111111111110

int allOnes = -1;  // 11111111111111111111111111111111 (32 ones)
System.out.println(allOnes >>> 28);  // 15  (0b1111)

Try It — Copy & Test

// === Save as BitwiseOps.java ===
public class BitwiseOps {
    public static void main(String[] args) {
        int a = 0b1010, b = 0b1100;
        System.out.println("AND: " + (a & b));   // 8
        System.out.println("OR:  " + (a | b));   // 14
        System.out.println("XOR: " + (a ^ b));   // 6
        System.out.println("NOT: " + (~a));       // -11
        System.out.println("<<:  " + (1 << 3));   // 8
        System.out.println(">>:  " + (-8 >> 2));   // -2
        System.out.println(">>>: " + (-1 >>> 28)); // 15
    }
}

// === Compile & Run ===
// $ javac BitwiseOps.java && java BitwiseOps
AND: 8
OR:  14
XOR: 6
NOT: -11
<<:  8
>>:  -2
>>>: 15

XOR Truth Table

XOR (exclusive or) returns 1 when exactly one of the two input bits is 1.

Four Fundamental XOR Properties

These four properties are the reason XOR appears in so many algorithms and exam questions:

1. Self-cancellation: a ^ a = 0 — any value XORed with itself produces zero.
2. Identity: a ^ 0 = a — XOR with zero changes nothing.
3. Commutative: a ^ b = b ^ a — order does not matter.
4. Associative: (a ^ b) ^ c = a ^ (b ^ c) — grouping does not matter.

Proof by Example

int a = 42;
System.out.println(a ^ a);       // 0     (self-cancellation)
System.out.println(a ^ 0);       // 42    (identity)
System.out.println(a ^ 7 ^ 7);   // 42    (7 cancels itself)
System.out.println((3 ^ 5) ^ 9); // 15    (associative)
System.out.println(3 ^ (5 ^ 9)); // 15    (same result)

Try It — Copy & Test

// === Save as XorTest.java ===
public class XorTest {
    public static void main(String[] args) {
        System.out.println(5 ^ 5);        // 0  (self-cancel)
        System.out.println(5 ^ 0);        // 5  (identity)
        System.out.println(3 ^ 5 ^ 3);    // 5  (cancel out 3s)
        System.out.println((3 ^ 5) ^ 7);  // same as 3 ^ (5 ^ 7)
        System.out.println(3 ^ (5 ^ 7));  // proves associativity
    }
}

// === Compile & Run ===
// $ javac XorTest.java && java XorTest
0
5
5
1
1

The Problem: Java Has No Unsigned Types

Unlike C/C++, Java's int is always signed: it ranges from -2³¹ (-2,147,483,648) to 2³¹-1 (2,147,483,647). There is no unsigned int keyword. The same 32 bits can represent completely different values depending on interpretation:

Java 8+ Unsigned Utility Methods

Java 8 added static methods to the Integer and Long wrapper classes that treat the raw bits as unsigned values:

Code Example

int x = -1;
System.out.println(x);                              // -1
System.out.println(Integer.toUnsignedLong(x));       // 4294967295
System.out.println(Integer.toUnsignedString(x));     // "4294967295"
System.out.println(Integer.toBinaryString(x));       // 11111111111111111111111111111111

Try It — Copy & Test

// === Save as UnsignedTest.java ===
public class UnsignedTest {
    public static void main(String[] args) {
        int x = -1;
        System.out.println(x);                            // -1
        System.out.println(Integer.toUnsignedLong(x));     // 4294967295
        System.out.println(Integer.toUnsignedString(x));   // 4294967295
        System.out.println(Integer.compareUnsigned(-1, 1)); // positive (unsigned -1 > 1)
        System.out.println(Integer.toBinaryString(x));     // 32 ones
    }
}

// === Compile & Run ===
// $ javac UnsignedTest.java && java UnsignedTest
-1
4294967295
4294967295
1
11111111111111111111111111111111

The Simple Sequential XOR Reduction

A reduction (also called a fold) takes a collection of values and combines them into a single result using a binary operator. For XOR, we start with the identity element (0) and XOR each value in sequence:

int xorAll(int[] arr) {
    int result = 0;              // identity: a ^ 0 = a
    for (int val : arr) {
        result ^= val;
    }
    return result;
}

Why result = 0?

Because 0 is the identity element for XOR. Starting from 0 means the first XOR operation gives 0 ^ arr[0] = arr[0], which is correct. If we started from any other value, it would pollute the result.

Try It — Copy & Test

// === Save as XorReduce.java ===
public class XorReduce {
    public static void main(String[] args) {
        int[] arr = {3, 5, 7, 3, 5};
        int result = 0;
        for (int val : arr) result ^= val;
        System.out.println(result);  // 7 (3^3=0, 5^5=0, leaves 7)
    }
}

// === Compile & Run ===
// $ javac XorReduce.java && java XorReduce
7

The Four-Step Pattern

Concurrent reduction follows a clean four-step pattern that works for any associative operation:

1. Split the array into chunks (one per thread).
2. Reduce each chunk independently in its own thread.
3. Wait for all threads to finish (join()).
4. Combine the partial results into the final answer.

Full Implementation

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        int nThreads = 4;
        int chunkSize = (n + nThreads - 1) / nThreads;  // ceiling division
        int[] partial = new int[nThreads];
        Thread[] threads = new Thread[nThreads];

        for (int t = 0; t < nThreads; t++) {
            final int ti = t;
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, n);
            threads[t] = new Thread(() -> {
                int xor = 0;
                for (int i = start; i < end; i++) {
                    xor ^= arr[i];
                }
                partial[ti] = xor;
            });
            threads[t].start();
        }

        for (Thread th : threads) th.join();

        int result = 0;
        for (int p : partial) result ^= p;

        System.out.println(Integer.toUnsignedString(result));
    }
}

Detailed Trace

Why No Synchronization Is Needed

Why final Is Required

Lambda expressions can only capture effectively final variables. That is why we write final int ti = t inside the loop. Without this, the lambda would try to capture the loop variable t, which changes on each iteration, and the compiler would reject it.

for (int t = 0; t < nThreads; t++) {
    final int ti = t;        // captured by lambda (effectively final)
    final int start = t * chunkSize;
    final int end = Math.min(start + chunkSize, n);
    threads[t] = new Thread(() -> {
        // ti, start, end are all effectively final here
        partial[ti] = /* ... */;
    });
}

Ceiling Division Explained

The formula (n + nThreads - 1) / nThreads computes the ceiling of n / nThreads using integer arithmetic. This ensures the chunks cover all elements, even when n is not evenly divisible.

Try It — Copy & Test

// === Save as ConcurrentXor.java ===
public class ConcurrentXor {
    public static void main(String[] args) throws Exception {
        int[] arr = {3, 5, 7, 9, 11, 13};
        int k = 3;
        int chunkSize = (arr.length + k - 1) / k;
        int[] partial = new int[k];
        Thread[] threads = new Thread[k];

        for (int t = 0; t < k; t++) {
            final int ti = t;
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, arr.length);
            threads[t] = new Thread(() -> {
                int xor = 0;
                for (int i = start; i < end; i++) xor ^= arr[i];
                partial[ti] = xor;
            });
            threads[t].start();
        }
        for (Thread th : threads) th.join();

        int result = 0;
        for (int p : partial) result ^= p;
        System.out.println(result);  // 3^5^7^9^11^13
        System.out.println(Integer.toUnsignedString(result));
    }
}

// === Compile & Run ===
// $ javac ConcurrentXor.java && java ConcurrentXor
14
14

A Different Pattern: One Number Per Thread

Session 1 asked: “Accept a different number in each thread, do some operations, print the values.” This is not chunk-based reduction. Each thread works on ONE input independently.

The Template

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] inputs = new int[n];
        for (int i = 0; i < n; i++) inputs[i] = sc.nextInt();

        int[] results = new int[n];       // each thread writes its own slot
        Thread[] threads = new Thread[n];

        for (int i = 0; i < n; i++) {
            final int idx = i;              // must be final for lambda
            threads[i] = new Thread(() -> {
                int val = inputs[idx];
                // === YOUR OPERATION HERE ===
                int lowBits  = val & 0xFF;           // extract lower 8 bits
                int highBits = (val >>> 8) & 0xFF;  // extract bits 8-15
                results[idx] = lowBits ^ highBits;   // XOR them
            });
            threads[i].start();
        }

        for (Thread t : threads) t.join();  // wait for all

        for (int r : results) System.out.println(r);
    }
}

Bit Extraction Patterns (Common Exam Operations)

The exam says “take some bits, perform bitwise ops.” Here are the building blocks:

Example: Each Thread Processes Its Number

Suppose the exam says: “Each thread takes its number, splits into two 16-bit halves, XORs them, and stores the result.”

threads[i] = new Thread(() -> {
    int val = inputs[idx];
    int lower = val & 0xFFFF;            // lower 16 bits
    int upper = (val >>> 16) & 0xFFFF;  // upper 16 bits
    results[idx] = lower ^ upper;        // XOR halves
});

Example: Thread Generates and Combines

Suppose: “Each thread generates a sequence from its number, then combines.”

threads[i] = new Thread(() -> {
    int val = inputs[idx];
    int result = 0;
    for (int bit = 0; bit < 32; bit++) {
        if ((val & (1 << bit)) != 0) {  // if bit is set
            result += (bit + 1);          // add position (1-indexed)
        }
    }
    results[idx] = result;
});

Try It — Copy & Test

// === Save as PerThread.java ===
public class PerThread {
    public static void main(String[] args) throws Exception {
        int[] inputs = {0xFF00, 0x1234, 0xABCD};
        int[] results = new int[inputs.length];
        Thread[] threads = new Thread[inputs.length];

        for (int i = 0; i < inputs.length; i++) {
            final int idx = i;
            threads[i] = new Thread(() -> {
                int val = inputs[idx];
                int low = val & 0xFF;
                int high = (val >>> 8) & 0xFF;
                results[idx] = low ^ high;
            });
            threads[i].start();
        }
        for (Thread t : threads) t.join();

        for (int r : results) System.out.println(r);
    }
}

// === Compile & Run ===
// $ javac PerThread.java && java PerThread
255
38
102

Using accumulateAndGet

Instead of per-thread slots, you can use a single shared AtomicInteger and atomically merge each thread's partial result into it. The accumulateAndGet method atomically applies a binary function to the current value and a given operand:

import java.util.concurrent.atomic.AtomicInteger;

AtomicInteger result = new AtomicInteger(0);

// Inside each thread, after computing local XOR:
int localXor = /* xor of this thread's chunk */;
result.accumulateAndGet(localXor, (a, b) -> a ^ b);

accumulateAndGet(x, fn) atomically sets the value to fn(currentValue, x) and returns the new value. Internally, it uses a Compare-And-Swap (CAS) loop, so it is lock-free and thread-safe.

Manual CAS Loop

If the exam asks you to implement the CAS loop yourself (or if you need custom logic), here is the explicit version:

int localXor = /* xor of this thread's chunk */;
int prev, next;
do {
    prev = result.get();
    next = prev ^ localXor;
} while (!result.compareAndSet(prev, next));

This loop keeps retrying until the CAS succeeds. It is the fundamental building block of lock-free concurrency in Java.

Complete AtomicInteger Example

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        int nThreads = 4;
        int chunkSize = (n + nThreads - 1) / nThreads;
        AtomicInteger result = new AtomicInteger(0);
        Thread[] threads = new Thread[nThreads];

        for (int t = 0; t < nThreads; t++) {
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, n);
            threads[t] = new Thread(() -> {
                int xor = 0;
                for (int i = start; i < end; i++) {
                    xor ^= arr[i];
                }
                result.accumulateAndGet(xor, (a, b) -> a ^ b);
            });
            threads[t].start();
        }

        for (Thread th : threads) th.join();
        System.out.println(Integer.toUnsignedString(result.get()));
    }
}

Try It — Copy & Test

// === Save as AtomicXor.java ===
import java.util.concurrent.atomic.AtomicInteger;

public class AtomicXor {
    public static void main(String[] args) throws Exception {
        int[] arr = {3, 5, 7, 9};
        AtomicInteger result = new AtomicInteger(0);
        Thread[] threads = new Thread[arr.length];

        for (int i = 0; i < arr.length; i++) {
            final int val = arr[i];
            threads[i] = new Thread(() -> {
                result.accumulateAndGet(val, (a, b) -> a ^ b);
            });
            threads[i].start();
        }
        for (Thread t : threads) t.join();

        System.out.println(result.get());  // 3^5^7^9
    }
}

// === Compile & Run ===
// $ javac AtomicXor.java && java AtomicXor
8

Associative Operations & Their Identities

The concurrent reduction pattern works for any associative operation. You only need to change the identity element and the combine step:

Concurrent Sum Example

The only change from the XOR version: replace ^= with += and ^ with + in the combine step.

int nThreads = 4;
int chunkSize = (n + nThreads - 1) / nThreads;
long[] partial = new long[nThreads];  // use long to avoid overflow
Thread[] threads = new Thread[nThreads];

for (int t = 0; t < nThreads; t++) {
    final int ti = t;
    final int start = t * chunkSize;
    final int end = Math.min(start + chunkSize, n);
    threads[t] = new Thread(() -> {
        long sum = 0;             // identity for addition
        for (int i = start; i < end; i++) {
            sum += arr[i];            // += instead of ^=
        }
        partial[ti] = sum;
    });
    threads[t].start();
}

for (Thread th : threads) th.join();

long total = 0;
for (long p : partial) total += p;  // + instead of ^
System.out.println(total);

Try It — Copy & Test

// === Save as ConcurrentSum.java ===
public class ConcurrentSum {
    public static void main(String[] args) throws Exception {
        int[] arr = {10, 20, 30, 40};
        int k = 2, chunkSize = 2;
        long[] partial = new long[k];
        Thread[] threads = new Thread[k];

        for (int t = 0; t < k; t++) {
            final int ti = t, start = t * chunkSize;
            final int end = Math.min(start + chunkSize, arr.length);
            threads[t] = new Thread(() -> {
                long sum = 0;
                for (int i = start; i < end; i++) sum += arr[i];
                partial[ti] = sum;
            });
            threads[t].start();
        }
        for (Thread th : threads) th.join();

        long total = 0;
        for (long p : partial) total += p;
        System.out.println(total);  // 100
    }
}

// === Compile & Run ===
// $ javac ConcurrentSum.java && java ConcurrentSum
100

Find the Unique Element (every other appears twice)

Given an array where every element appears exactly twice except one, find the unique element. Because a ^ a = 0, all pairs cancel out, leaving only the unique value.

int[] arr = {3, 5, 3, 7, 5};
int unique = 0;
for (int x : arr) unique ^= x;
// unique = 7
// Because: 3^5^3^7^5 = (3^3)^(5^5)^7 = 0^0^7 = 7

Find the Missing Number in [0..n]

Given an array of n integers containing all values from 0 to n except one, find the missing number. XOR all values 0 through n, then XOR with every array element. All present values cancel, leaving the missing one.

int findMissing(int[] arr, int n) {
    int xor = 0;
    for (int i = 0; i <= n; i++) xor ^= i;   // XOR of 0..n
    for (int x : arr) xor ^= x;               // cancel present values
    return xor;
}

Swap Two Variables Without a Temporary

The classic XOR swap trick uses three XOR operations:

int a = 5, b = 9;

a ^= b;  // a = a^b         (a=12, b=9)
b ^= a;  // b = b^(a^b) = a (a=12, b=5)
a ^= b;  // a = (a^b)^a = b (a=9,  b=5)

// Now a=9, b=5. Swapped!

How it works: after the first line, a holds a^b. The second line XORs b with a^b, which cancels the original b and leaves the original a. The third line XORs the stored a^b with the now-recovered original a, canceling it and leaving the original b.

Summary of XOR Tricks

Try It — Copy & Test

// === Save as XorTricks.java ===
public class XorTricks {
    public static void main(String[] args) {
        // Find unique: every element appears twice except one
        int[] arr = {2, 3, 5, 3, 2};
        int unique = 0;
        for (int x : arr) unique ^= x;
        System.out.println("Unique: " + unique);  // 5

        // Find missing: array has 0..5 except one
        int[] missing = {0, 1, 3, 4, 5};
        int xor = 0;
        for (int i = 0; i <= 5; i++) xor ^= i;
        for (int x : missing) xor ^= x;
        System.out.println("Missing: " + xor);  // 2

        // Swap without temp
        int a = 10, b = 25;
        a ^= b; b ^= a; a ^= b;
        System.out.println("a=" + a + " b=" + b);  // a=25 b=10
    }
}

// === Compile & Run ===
// $ javac XorTricks.java && java XorTricks
Unique: 5
Missing: 2
a=25 b=10

Java's Built-in Bit Methods

The Integer class provides several useful bit manipulation methods that are heavily optimized (often map to single CPU instructions):

Integer.bitCount(x)                // count set bits (number of 1s)
Integer.highestOneBit(x)           // isolate the highest set bit
Integer.lowestOneBit(x)            // isolate the lowest set bit
Integer.numberOfLeadingZeros(x)    // zeros before the highest 1
Integer.numberOfTrailingZeros(x)   // zeros after the lowest 1
Integer.reverse(x)                 // reverse all 32 bits
Integer.reverseBytes(x)            // reverse byte order (endianness)
Integer.toBinaryString(x)          // "10110..." string representation

Examples

int x = 0b10110100;  // 180 in decimal

System.out.println(Integer.bitCount(x));              // 4 (four 1-bits)
System.out.println(Integer.highestOneBit(x));          // 128 (0b10000000)
System.out.println(Integer.numberOfLeadingZeros(x));   // 24 (32 - 8 = 24)
System.out.println(Integer.numberOfTrailingZeros(x));  // 2 (two trailing 0s)
System.out.println(Integer.toBinaryString(x));         // "10110100"

Common Single-Bit Operations

These four operations manipulate a specific bit at position k (0-indexed from the right):

Examples

int x = 0b1010;  // 10 in decimal

// Check bit 1 (second from right)
System.out.println((x & (1 << 1)) != 0);  // true  (bit 1 is set)
System.out.println((x & (1 << 0)) != 0);  // false (bit 0 is not set)

// Set bit 0
System.out.println(Integer.toBinaryString(x | (1 << 0)));   // "1011"

// Clear bit 1
System.out.println(Integer.toBinaryString(x & ~(1 << 1)));  // "1000"

// Toggle bit 3
System.out.println(Integer.toBinaryString(x ^ (1 << 3)));   // "10" (was 1, now 0)

Try It — Copy & Test

// === Save as BitUtils.java ===
public class BitUtils {
    public static void main(String[] args) {
        int x = 42;  // 0b101010
        System.out.println("bitCount: " + Integer.bitCount(x));      // 3
        System.out.println("highBit:  " + Integer.highestOneBit(x)); // 32
        System.out.println("binary:   " + Integer.toBinaryString(x)); // 101010

        // Check bit 3 (0-indexed from right)
        System.out.println("bit 3 set? " + ((x & (1 << 3)) != 0));  // true
        // Set bit 0
        System.out.println("set bit 0: " + (x | 1));                // 43
        // Toggle bit 1
        System.out.println("toggle bit 1: " + (x ^ (1 << 1)));     // 40
    }
}

// === Compile & Run ===
// $ javac BitUtils.java && java BitUtils
bitCount: 3
highBit:  32
binary:   101010
bit 3 set? true
set bit 0: 43
toggle bit 1: 40

Binary Notation in Java

Java supports three number bases in source code:

int decimal    = 42;         // base 10 (normal)
int binary     = 0b101010;   // base 2  (prefix 0b)
int octal      = 052;        // base 8  (prefix 0)  -- avoid, confusing
int hex        = 0x2A;       // base 16 (prefix 0x)

// Underscores for readability (Java 7+):
int readable   = 0b0010_1010;  // same as 0b101010 = 42
int mask16     = 0xFFFF;       // lower 16 bits mask = 65535
int mask8      = 0xFF;         // lower 8 bits mask = 255

Signed vs Unsigned: Two’s Complement

Java’s int is 32 bits using two’s complement. The highest bit (bit 31) is the sign bit:

How Negation Works (Two’s Complement)

To negate a number: flip all bits, then add 1.

//  5 in binary (8-bit): 0000_0101
// flip all bits:        1111_1010
// add 1:                1111_1011 = -5

// In Java:
int x = 5;
int neg = ~x + 1;    // -5  (~ flips bits, +1 completes two's complement)
// equivalent to: int neg = -x;

Sizes in Java

The Two Right Shifts

int x = -8;  // binary: 1111...1000

x >> 2;     // Arithmetic shift: -2  (fills with sign bit 1)
             // 1111...1110

x >>> 2;    // Logical shift: 1073741822  (fills with 0)
             // 0011...1110

Printing Binary for Debugging

int x = 42;
System.out.println(Integer.toBinaryString(x));  // "101010"
System.out.println(Integer.toHexString(x));     // "2a"
System.out.println(Integer.toOctalString(x));   // "52"

// Pad to 32 bits:
String bin = String.format("%32s", Integer.toBinaryString(x)).replace(' ', '0');
// "00000000000000000000000000101010"

Try It — Copy & Test

// === Save as BinaryDemo.java ===
public class BinaryDemo {
    public static void main(String[] args) {
        // Notation
        System.out.println(0b1010);   // 10
        System.out.println(0xFF);     // 255
        System.out.println(0b0010_1010); // 42

        // Signed vs unsigned
        int neg = -1;
        System.out.println(Integer.toBinaryString(neg));  // 32 ones
        System.out.println(Integer.toUnsignedString(neg)); // 4294967295

        // Negation: flip + 1
        int x = 5;
        System.out.println(~x + 1);  // -5

        // >> vs >>>
        System.out.println(-8 >> 2);   // -2
        System.out.println(-8 >>> 2);  // 1073741822
    }
}

// === Compile & Run ===
// $ javac BinaryDemo.java && java BinaryDemo
10
255
42
11111111111111111111111111111111
4294967295
-5
-2
1073741822

Problem: Concurrent Unsigned XOR Reduction

Task: Read N integers from stdin. Compute their XOR using K threads concurrently. Print the result as an unsigned integer.

Input: First line contains N (number of integers) and K (number of threads). Second line contains N space-separated integers.

Output: Single line with the unsigned XOR of all integers.

Complete Solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();        // number of threads
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int chunkSize = (n + k - 1) / k;    // ceiling division
        int[] partial = new int[k];          // one slot per thread
        Thread[] threads = new Thread[k];

        for (int t = 0; t < k; t++) {
            final int ti = t;
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, n);
            threads[t] = new Thread(() -> {
                int xor = 0;
                for (int i = start; i < end; i++) {
                    xor ^= arr[i];
                }
                partial[ti] = xor;
            });
            threads[t].start();
        }

        // Wait for all threads to complete
        for (Thread th : threads) {
            th.join();
        }

        // Combine partial results
        int result = 0;
        for (int p : partial) {
            result ^= p;
        }

        // Print as UNSIGNED integer
        System.out.println(Integer.toUnsignedString(result));
    }
}

Sample Run

Note: -1 ^ 0 ^ 0 = -1 as signed, but 4294967295 as unsigned. If you print -1 instead, you lose points.

Alternative: If Input Only Has N (no K)

Some problem variants only give N integers and expect you to choose the number of threads yourself. In that case, just hardcode k = 4 (or whatever the problem suggests):

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        int k = 4;  // choose number of threads
        int chunkSize = (n + k - 1) / k;
        int[] partial = new int[k];
        Thread[] threads = new Thread[k];

        for (int t = 0; t < k; t++) {
            final int ti = t;
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, n);
            threads[t] = new Thread(() -> {
                int xor = 0;
                for (int i = start; i < end; i++) xor ^= arr[i];
                partial[ti] = xor;
            });
            threads[t].start();
        }
        for (Thread th : threads) th.join();

        int result = 0;
        for (int p : partial) result ^= p;
        System.out.println(Integer.toUnsignedString(result));
    }
}

Try It — Run Locally

// === Save the program above as Main.java ===
// === Create input.txt: ===
// 8
// 3 5 7 3 5 9 7 9

// === Compile & Run: ===
// $ javac Main.java && java Main < input.txt
0

// (All values cancel out: 3^5^7^3^5^9^7^9 = 0)

Problem 1: Concurrent XOR Reduction

Read N integers from stdin. Use 4 threads to compute the XOR of all integers. Print the result as an unsigned integer.

Sample Input

8
3 5 7 3 5 9 7 9

Expected Output

0

Explanation: All values appear in pairs, so every pair cancels out via XOR. 3^5^7^3^5^9^7^9 = (3^3)^(5^5)^(7^7)^(9^9) = 0^0^0^0 = 0.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        int nThreads = 4;
        int chunkSize = (n + nThreads - 1) / nThreads;
        int[] partial = new int[nThreads];
        Thread[] threads = new Thread[nThreads];

        for (int t = 0; t < nThreads; t++) {
            final int ti = t;
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, n);
            threads[t] = new Thread(() -> {
                int xor = 0;
                for (int i = start; i < end; i++) xor ^= arr[i];
                partial[ti] = xor;
            });
            threads[t].start();
        }

        for (Thread th : threads) th.join();

        int result = 0;
        for (int p : partial) result ^= p;
        System.out.println(Integer.toUnsignedString(result));
    }
}

Problem 2: Concurrent Sum with AtomicLong

Read N integers from stdin. Use 4 threads to compute the sum of all integers. Use AtomicLong for the shared result (instead of per-thread slots). Print the sum.

Sample Input

6
10 20 30 40 50 60

Expected Output

210

import java.util.Scanner;
import java.util.concurrent.atomic.AtomicLong;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        int nThreads = 4;
        int chunkSize = (n + nThreads - 1) / nThreads;
        AtomicLong result = new AtomicLong(0);
        Thread[] threads = new Thread[nThreads];

        for (int t = 0; t < nThreads; t++) {
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, n);
            threads[t] = new Thread(() -> {
                long localSum = 0;
                for (int i = start; i < end; i++) {
                    localSum += arr[i];
                }
                // Atomically add the local sum to the shared result
                result.addAndGet(localSum);
            });
            threads[t].start();
        }

        for (Thread th : threads) th.join();
        System.out.println(result.get());
    }
}

Problem 3: Find the Unique Element

Given N integers where every element appears exactly twice except one, find the unique element using XOR. Single-threaded solution.

Sample Input

5
2 3 5 3 2

Expected Output

5

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int unique = 0;
        for (int i = 0; i < n; i++) {
            unique ^= sc.nextInt();
        }
        System.out.println(unique);
    }
}

Problem 4: Concurrent Min/Max

Read N integers from stdin. Use 4 threads to find both the minimum and maximum values concurrently. Print the minimum on the first line and the maximum on the second line.

Sample Input

8
42 17 93 5 78 31 66 12

Expected Output

5
93

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        int nThreads = 4;
        int chunkSize = (n + nThreads - 1) / nThreads;
        int[] partialMin = new int[nThreads];
        int[] partialMax = new int[nThreads];
        Thread[] threads = new Thread[nThreads];

        // Initialize with identity elements
        for (int i = 0; i < nThreads; i++) {
            partialMin[i] = Integer.MAX_VALUE;
            partialMax[i] = Integer.MIN_VALUE;
        }

        for (int t = 0; t < nThreads; t++) {
            final int ti = t;
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, n);
            threads[t] = new Thread(() -> {
                int localMin = Integer.MAX_VALUE;
                int localMax = Integer.MIN_VALUE;
                for (int i = start; i < end; i++) {
                    if (arr[i] < localMin) localMin = arr[i];
                    if (arr[i] > localMax) localMax = arr[i];
                }
                partialMin[ti] = localMin;
                partialMax[ti] = localMax;
            });
            threads[t].start();
        }

        for (Thread th : threads) th.join();

        int globalMin = Integer.MAX_VALUE;
        int globalMax = Integer.MIN_VALUE;
        for (int i = 0; i < nThreads; i++) {
            if (partialMin[i] < globalMin) globalMin = partialMin[i];
            if (partialMax[i] > globalMax) globalMax = partialMax[i];
        }

        System.out.println(globalMin);
        System.out.println(globalMax);
    }
}

Problem 5: CAS-based XOR Accumulator

Implement a thread-safe XOR accumulator using AtomicInteger and a manual CAS loop (do NOT use accumulateAndGet). Read N integers, use 4 threads, and print the unsigned XOR result.

Sample Input

4
1 2 3 4

Expected Output

4

Explanation: 1 ^ 2 = 3, 3 ^ 3 = 0, 0 ^ 4 = 4.

import java.util.Scanner;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        int nThreads = 4;
        int chunkSize = (n + nThreads - 1) / nThreads;
        AtomicInteger result = new AtomicInteger(0);
        Thread[] threads = new Thread[nThreads];

        for (int t = 0; t < nThreads; t++) {
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, n);
            threads[t] = new Thread(() -> {
                // Step 1: compute local XOR for this chunk
                int localXor = 0;
                for (int i = start; i < end; i++) {
                    localXor ^= arr[i];
                }

                // Step 2: merge into shared result using CAS loop
                int prev, next;
                do {
                    prev = result.get();
                    next = prev ^ localXor;
                } while (!result.compareAndSet(prev, next));
            });
            threads[t].start();
        }

        for (Thread th : threads) th.join();
        System.out.println(Integer.toUnsignedString(result.get()));
    }
}

Problem 6: Count Set Bits Concurrently

Read N integers from stdin. Use 4 threads to count the total number of set bits (1s) across all integers. Print the total count.

Hint: use Integer.bitCount().

Sample Input

4
7 15 3 8

Expected Output

11

Explanation: 7 = 0b111 (3 bits), 15 = 0b1111 (4 bits), 3 = 0b11 (2 bits), 8 = 0b1000 (1 bit). Total = 3 + 4 + 2 + 1 = 10.

Wait — let us recount: 7 has 3 set bits, 15 has 4, 3 has 2, 8 has 1. That is 3+4+2+1 = 10. So the output is:

Corrected Expected Output

10

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        int nThreads = 4;
        int chunkSize = (n + nThreads - 1) / nThreads;
        int[] partial = new int[nThreads];
        Thread[] threads = new Thread[nThreads];

        for (int t = 0; t < nThreads; t++) {
            final int ti = t;
            final int start = t * chunkSize;
            final int end = Math.min(start + chunkSize, n);
            threads[t] = new Thread(() -> {
                int count = 0;
                for (int i = start; i < end; i++) {
                    count += Integer.bitCount(arr[i]);
                }
                partial[ti] = count;
            });
            threads[t].start();
        }

        for (Thread th : threads) th.join();

        int total = 0;
        for (int p : partial) total += p;
        System.out.println(total);
    }
}

Exam Day Checklist