Invert k-th Most Significant Bits of N in Java

2025年5月9日 | 阅读 3 分钟

问题陈述

反转数字 N 的第 k 个最高有效位 (MSB) 涉及翻转从最左侧位开始计数的第 k 个位置的位。

问题解决方案

过程如下

创建掩码：一个在第 k 个位置为 1 的掩码。
使用 XOR：应用 XOR 来反转位。如果位是 1，则变为 0；如果位是 0，则变为 1。

例如，对于 N = 59 (二进制 111011) 和 k = 3，反转第 3 位得到 51 (二进制表示 110011)。此技术在位操作中用于标志操作等任务。

示例 1

输入：N = 10, K = 1

输出 2

10 的二进制形式是 1010。当第一位被反转时，它变成 0010，其十进制值为 2。

示例 2

输入：N = 32, K = 2

输出 48

32 的二进制形式是 100000。通过翻转第二位，它变为 110000，其十进制值为 48。

位操作方法

首先，确定 N 中位的总数。如果位的数量小于 K，则返回 N 作为结果。否则，翻转 N 的第 K 个最高有效位，然后返回翻转后的新数字。

算法

步骤 1：确定 n 的二进制表示所需的位数，并将二进制数字保存在数组中。

步骤 2：如果 k 大于 n 中的总位数，则不更改地返回 n。

步骤 3：通过切换其值（从 0 到 1 或从 1 到 0）来更改二进制数组中的第 k 位。

步骤 4：计算更新后的二进制数组的十进制值。

步骤 5：输出翻转第 k 位后得到的十进制值。

实施

public class BitFlipper {
    // Function to convert a decimal number to binary and store it in an array
    static void decimalToBinary(int arr[], int n) { 
        int bitCount = (int)(Math.log(n) / Math.log(2)); 
        while (n > 0) { 
            // Store the current bit in the array
            arr[bitCount--] = n % 2; 
            // Divide the number by 2 to shift right
            n /= 2; 
        } 
    } 
    // Function to convert a binary array to its decimal equivalent
    static int binaryToDecimal(int arr[], int length) { 
        // Initialize the result variable
        int result = 0; 
        // Iterate over the binary array to calculate the decimal value
        for (int i = 0; i < length; i++) 
            // Add the value of the bit at position i shifted to the correct place
            result += arr[i] << (length - i - 1); 
        // Return the final decimal result
        return result; 
    } 
    // Function to flip the k-th most significant bit of a number
    static int flipKthBit(int n, int k) { 
        int numOfBits = (int)(Math.log(n) / Math.log(2)) + 1; 
        // Create an array to store the binary representation of n
        int binary[] = new int[numOfBits]; 
        // Convert the decimal number into binary and store it in the array
        decimalToBinary(binary, n); 
        // Check if k is larger than the number of bits in n
        if (k > numOfBits) 
            // If yes, return n as the number of bits is less than k
            return n; 
        binary[k - 1] = (binary[k - 1] == 0) ? 1 : 0; 
        // Convert the modified binary array back to its decimal equivalent
        return binaryToDecimal(binary, numOfBits); 
    } 
    // Main function to test the program
    public static void main (String[] args) { 
        // Define the input number n and the bit position k to flip
        int n = 45; // Modified input number (binary: 101101)
        int k = 3;  // Modified position of the bit to flip (3rd most significant bit)
        // Print the result of flipping the k-th bit of n
        System.out.println(flipKthBit(n, k));
    } 
}   

输出

时间和空间复杂度：O((log(m)+log(n))

下一主题如何在 Java 中解决 IllegalStateException

Invert k-th Most Significant Bits of N in Java

问题陈述

问题解决方案

位操作方法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Invert k-th Most Significant Bits of N in Java

问题陈述

问题解决方案

位操作方法

算法

实施

相关帖子

Nested Loops in Java

如何在 Java 中删除字符串的子串

Java 中 print() 与 println() 的区别

Java 中查找直线上的最大点数

Sierpinski Number in Java

Find the Sequence of Strings Appeared on the Screen in Java

Java 中将字节转换为图像

Hardy-Ramanujan Theorem in Java

Java Does Not Open

Types of Variables in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器