切换一个数字的第一个和最后一个位

2023年 8月 28日 55.6k 0

切换一个数字的第一个和最后一个位

The following article provides an in depth explanation of the method used to modify a number by toggling its first and last bit using bitwise operators. A bitwise operator is an operator that can be used to manipulate individual bits in binary numbers or bit patterns.

Problem Statement

For a given number n, modify the number such that the first and the last bit of the binary expansion of the new number are flipped i.e. if the original bit is 1 then the flipped bit should be 0 and vice versa. All the bits between the first and the last bit should be left unchanged.

Examples

Input: 13

登录后复制

Output: 4

登录后复制

Explanation

的中文翻译为:

解释

The binary expansion of 13 is 1101.

在切换第一个和最后一个位之后,扩展变为0100,等于4。

因此,输出结果为4。

Input: 27

登录后复制

Output: 10

登录后复制

Explanation

的中文翻译为:

解释

The binary expansion of 27 is 11011.

在切换第一个和最后一个位之后,扩展变为01010,等于10。

Hence the output is 10.

Input: 113

登录后复制

Output: 48

登录后复制

Explanation

的中文翻译为:

解释

The binary expansion of 113 is 1110001.

On toggling the first and the last bit, the expansion becomes 0110000 which is equal to 48.

Hence the output is 48.

Solution Approach

This approach makes use of the bitwise XOR and left shift operator. If the corresponding bit of both operands is different, the bitwise XOR operator evaluates to 1; otherwise, it evaluates to 0. We'll employ the bitwise XOR operator's ability to toggle a bit. For instance, if the first bit of the number, n, is 1, then n ^ 1 will cause the number's first bit to be 0. In addition, if the number's first bit is set to 0, the operation n ^ 1 will change it to 1.

要翻转数字n的第一个位,我们计算n ^ 1。它执行一个异或操作,将n的最低有效位或第一个位与1进行反转。

为了翻转最后一位,我们生成一个只有最后一位被设置的数字k。最后一位的位置r等于log2(n)。这是因为在n的二进制展开中使用了log2(n)位。

The following steps are performed to implement this approach −

  • If n = 1, display 0 and return.

  • Toggle the first bit of the number by taking an XOR of the n with 1.

  • 通过将n与1

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论