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

秋明君_7879

秋明君_7879

2023-08-27

1188人浏览

转载

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

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与1th位。

  • Display the answer.

干跑

首先让我们了解按位异或(^)运算符的工作原理。

Input Flag Input ^ Flag
0 0 0
0 1 1
1 0 1
1 1 0

可以观察到,当flag的值为1时,输入的值会被反转。

考虑数字57。57的二进制展开式是111001。

1 1 1 0 0 1

考虑一个新的数字1。

AlgForce AI
AlgForce AI

AlgForce AI是一款把 Excel 和 CSV 数据转换为分析报告、图表和演示稿的 AI 数据分析平台。

下载
0 0 0 0 0 1

要切换最低有效位或最左边的位,请执行57 ^ 1,结果为

1 1 1 0 0 0

The number 111000 is generated.

现在,为了切换最后一位,我们修改数字1,使得最后一位被设置,而不是第一位。为了做到这一点,我们必须将1左移log2(n)位,或者在这种情况下是log2(57),也就是5。在这样做之后,我们得到:

1 0 0 0 0 0

Computing XOR now gives us.

0 1 1 0 0 0

生成了数字01100,等于24。将其与原始数字57的二进制展开进行比较,可以观察到最终答案中的第一位和最后一位已经被切换。

因此,答案是24。

算法

函数 toggle_first_bit()

  • Compute n ^ 1

  • 更新 n

函数 toggle_last_bit()

  • 初始化 r = log2(n)

  • 初始化 k = 1

  • 计算 n ^ k

  • 更新 n

Function main()

  • 初始化 n

  • 如果 (n == 1)

    • return 0;

  • Function call toggle_first_bit().

  • 调用函数 toggle_last_bit()。

  • 显示 n.

示例:C++程序

This program modifies an input number n by toggling the first and the last bit of its binary expansion. It employs bitwise operator XOR and left shift operator to achieve its goal.

// This C++ program toggles the first and the last bit of a number
#include <iostream>
#include <cmath>
using namespace std;
// this function flips the last bit of the number
// it uses the concept that a log(n) bits are used in the binary expansion of a number n
void toggle_last_bit(int& n){
   int r = log2(n); // value of r indicates the count of last bit of n
   int k; // generate a number with log(n) where only the last bit is 1 using the left shift operator
   k = 1 <h3>输出</h3>
<pre class="brush:php;toolbar:false;">input number = 113
Number after Toggle First and Last Bits of a Number: 48

Time and Space Analysis

时间复杂度 - O(1),因为该算法始终在常数时间内工作,与输入数字无关。

空间复杂度 - O(1),因为在实现中没有使用辅助空间。

Conclusion

本文讨论了一种切换数字的第一个和最后一个位的方法。为了实现这一点,我们使用了位左移运算符来生成新的位模式,使用位异或运算符来计算结果。为了更深入地理解,详细解释了方法的概念、示例的演示、使用的算法、C++程序解决方案以及时间和空间复杂度分析。

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
java基础知识汇总
java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友,请阅读本专题下面的的有关文章,欢迎大家来php中文网学习。

2023.10.24

6424

49

Go语言中的运算符有哪些
Go语言中的运算符有哪些

Go语言中的运算符有:1、加法运算符;2、减法运算符;3、乘法运算符;4、除法运算符;5、取余运算符;6、比较运算符;7、位运算符;8、按位与运算符;9、按位或运算符;10、按位异或运算符等等。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.02.23

3584

5

php三元运算符用法
php三元运算符用法

本专题整合了php三元运算符相关教程,阅读专题下面的文章了解更多详细内容。

2025.10.17

1952

13

function是什么
function是什么

function是函数的意思,是一段具有特定功能的可重复使用的代码块,是程序的基本组成单元之一,可以接受输入参数,执行特定的操作,并返回结果。本专题为大家提供function是什么的相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.04

3760

5

js函数function用法
js函数function用法

js函数function用法有:1、声明函数;2、调用函数;3、函数参数;4、函数返回值;5、匿名函数;6、函数作为参数;7、函数作用域;8、递归函数。本专题提供js函数function用法的相关文章内容,大家可以免费阅读。

2023.10.07

614

5

点击input框没有光标怎么办
点击input框没有光标怎么办

点击input框没有光标的解决办法:1、确认输入框焦点;2、清除浏览器缓存;3、更新浏览器;4、使用JavaScript;5、检查硬件设备;6、检查输入框属性;7、调试JavaScript代码;8、检查页面其他元素;9、考虑浏览器兼容性。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2023.11.24

994

4

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7216

4

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习