import java.util.ArrayList;

import java.util.List;

public class hammingCode {

public static int calculateParityBits(int m, int low, int high) {

// Binary algorithm to find the required number of bits

if (high == 0) {

high = m + 1;

}

int r = (low + high) / 2;

if (low == high) {

return low;

} else if (Math.pow(2, r) >= r + m + 1) { // r = redundant bit, m = data bit

return calculateParityBits(m, low, r);

} else {

return calculateParityBits(m, r + 1, high);

}

}

public static boolean isPowerOfTwo(int num) {

// Performs a bitwise AND operation between num and num - 1.

// This operation turns off the rightmost set bit in num (i.e., the least significant bit).

// If the result of the bitwise AND operation is zero, it means that num had only one set bit (power of 2)

// before the bitwise operation, and that bit was turned off. In this case, the number is considered a power of 2.

return (num & (num - 1)) == 0;

}

public static int calculateParityValue(List<Character> encodedBlock, int pos) {

// Count the number of ones corresponding to the parity bit

int count = 0;

for (int i = 0; i < encodedBlock.size(); i++) {

int bit = encodedBlock.get(i);

if (bit == '1' && (((i + 1) & pos) != 0)) {

count++;

}

}

return count % 2;

}

public static String hammingEncode(String message) {

int m = message.length(); // Length of the message

int r = calculateParityBits(m, 0, 0); // Calculate the number of parity bits

int blockLength = m + r; // Total length of the encoded block

// Create a list to store the encoded bits

List<Character> encodedBlock = new ArrayList<>();

int dataBit = 0;

// Iterate over the block and copy the data

for (int position = 1; position <= blockLength; position++) {

if (isPowerOfTwo(position)) {

encodedBlock.add('P'); // Mark as parity bit

} else {

encodedBlock.add(message.charAt(dataBit)); // Data bit, copy from the message

dataBit++;

}

}

// Iterate over the parity bits in the encoded block

for (int position = 1; position <= blockLength; position++) {

if (encodedBlock.get(position - 1) == 'P') {

// Calculate and assign the required parity value

int parity = calculateParityValue(encodedBlock, position);

encodedBlock.set(position - 1, (parity % 2 == 0) ? '0' : '1');

}

}

// Convert the list of characters to a string

StringBuilder encodedMessage = new StringBuilder();

for (char bit : encodedBlock) {

encodedMessage.append(bit);

}

return encodedMessage.toString();

}

public static void main(String[] args) {

String message = "11110010010"; // Example message

String encodedMessage = hammingEncode(message);

System.out.println("Message entered: " + message);

System.out.println("Encoded Message: " + encodedMessage);

}

}