题目描述

写一函数，输入一个四位数字，要求输出这四个数字字符，但每两个数字间空格。如输入1990，应输出"1 9 9 0"。

输入

一个四位数

输出

增加空格输出

样例输入

1990

样例输出

1 9 9 0 

来源/分类

C语言

题目截图：

思路：

原来以为是自己输出四个数，再让他们输出就好啦。
本想，这不过是在这些数中增加一些空格而已~
后来提交之后答案错误~
哈哈，才审好题目！

不过，乍眼一看还是有难度的。不过，自己利用/ %运算就可以顺利解决啦！
但是最后一个数，不能输出空格！这个要留在最后进行输出！
void output(int a)
{int i=0;int s=1000;
	for(;i<z-1;i++)
	{
		cout<<a/s<<" ";
		a%=s;
		s/=10;
	}
	cout<<a;
}

代码：

#include<iostream>
using namespace std;
#define z 4
void output(int a)
{int i=0;int s=1000;
	for(;i<z-1;i++)
	{
		cout<<a/s<<" ";
		a%=s;
		s/=10;
	}
	cout<<a;
}
int main()
{
	int a;int i;
		cin>>a;
output(a);
}

代码截图：

运行结果：

OJ结果：

涉及到的几个概念

MDR：数据寄存器，用来存入内存中读入/写出的信息。
MAR：地址寄存器，用来存放当前CPU访问的内存单元地址

地址线与数据线

• 地址线的作用：地址线的作用就是决定了数据的存储单元的位置，也决定了你有多少个能够存放数据的存储单元个数，这点不懂没关系，后面会解释的。
• 数据线的作用：数据线的作用就是决定了二进制的数据。
• 举个例子：地址线就是你家的门牌号，数据线就是待在家里边的你。比如现在有人想要找你，就要通过门牌号来找到你，也就是通过地址线来找到数据线决定的数据。

字扩展与位扩展

Xk × X位 其中Xk就是代表字扩展里的字，X位就是代表位扩展里边的位。

1. 字扩展
   字扩展就是要增加存储字的数量，也就是地址线的位数
   举个栗子：现在我能搜索的门牌号范围只有一个村，现在我想能够搜索到一个镇的门牌号，怎么办？当然是要扩大能够搜索的范围呀，字扩展就是起到的这么一个作用。

• 例如利用1K×8位的DRAM芯片，设计2K×8位的DRAM存储器（字扩展）
  
  这里为什么要把A₁₀设置成片选端呢？因为它们不能同时工作，每个芯片提供8位数据，在数据线上会造成混乱，A₁₀做片选信号，控制选中哪个芯片。
• A₁₀等于0的时候范围是：A₁₀A₉A₈A₇A₆A₅A₄A₃A₂A₁A₀=00000000000-01111111111_B=0-1023
  第一个芯片会工作，当A₀到A₉都为1时再增加A₁₀就会变为1此时根据图可以看出CS₀非=1是高电平，A₁₀在经过一个非门使CS₁非接收到0，此时第二个芯片工作，从10000000000=1024开始。
• A₁₀等于1的时候范围是：A₁₀A₉A₈A₇A₆A₅A₄A₃A₂A₁A₀=10000000000-11111111111_B=1024-2047

扩展之前是0-1023，扩展之后是从0-2047.

这样就形成了字扩展。对应了上边的地址线作用中的定义，这样就扩大了存储单元的个数。

2. 位扩展
   
   位扩展就比较简单了，位扩展就是增大数据的范围，原本是四位D₀到D₃对应范围是0000-1111_B= 0 - 15；变为八位之后是D₀到D₇对应范围变成00000000 - 11111111_B=0 - 255；对应的图上的连线两个芯片八根数据线从D₀到D₇。一个芯片是数据的高四位，一个芯片是数据的低四位。

扩展之前是0-15，扩展之后0-255.

因为他们的地址线是连在一起的所以地址的范围两个芯片是一样的，对应的数据的地址也是一样的，取数据的时候根据地址取出第一个芯片的四位和第二个芯片的四位，最后形成八位的数据。

3. 字位扩展
   
   这里A₁₁A₁₀两个二进制数可以有00，01，10，11四种情况对应了四组二个芯片组成的八位存储器的选择。若有八个的话就要有A₁₂A₁₁A₁₀三个二进制数000,001,010,011,100,101,110,111来代表八组二个芯片组成的八位存储器。

如果觉得博主写的可以的话，动动你的小手点个赞吧。

位算法的效率有多快我就不说，不信你可以去用 10 亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这些技巧，当然，采用位运算，也是可以装逼的，不信，你往下看。我会从最简单的讲起，一道比一道难度递增，不过居然是讲技巧，那么也不会太难，相信你分分钟看懂。

判断奇偶数

判断一个数是基于还是偶数，相信很多人都做过，一般的做法的代码如下

if( n % 2) == 01
    // n 是个奇数
}

如果把 n 以二进制的形式展示的话，其实我们只需要判断最后一个二进制位是 1 还是 0 就行了，如果是 1 的话，代表是奇数，如果是 0 则代表是偶数，所以采用位运算的方式的话，代码如下：

if(n & 1 == 1){
    // n 是个奇数。
}

有人可能会说，我们写成 n % 2 的形式，编译器也会自动帮我们优化成位运算啊，这个确实，有些编译器确实会自动帮我们优化。但是，我们自己能够采用位运算的形式写出来，当然更好了。别人看到你的代码，我靠，牛逼啊。无形中还能装下逼，是不是。当然，时间效率也快很多，不信你去测试测试。

2、交换两个数

交换两个数相信很多人天天写过，我也相信你每次都会使用一个额外来变量来辅助交换，例如，我们要交换 x 与 y 值，传统代码如下：

int tmp = x;
x = y;
y = tmp;

这样写有问题吗？没问题，通俗易懂，万一哪天有人要为难你，**不允许你使用额外的辅助变量来完成交换呢？**你还别说，有人面试确实被问过，这个时候，位运算大法就来了。代码如下：

x = x ^ y   // （1）
y = x ^ y   // （2）
x = x ^ y   // （3）

我靠，牛逼！三个都是 x ^ y，就莫名交换成功了。在此我解释下吧，我们知道，两个相同的数异或之后结果会等于 0，即 n ^ n = 0。并且任何数与 0 异或等于它本身，即 n ^ 0 = n。所以，解释如下：

把（1）中的 x 带入 （2）中的 x，有

y = x^y = (x^y)y = x^(yy) = x^0 = x。 x 的值成功赋给了 y。

对于（3）,推导如下：

x = x^y = (x^y)x = (x^x)y = 0^y = y。

这里解释一下，异或运算支持运算的交换律和结合律哦。

以后你要是别人看不懂你的代码，逼格装高点，就可以在代码里面采用这样的公式来交换两个变量的值了，被打了不要找我。

讲这个呢，是想告诉你位运算的强大，让你以后能够更多着去利用位运算去解决一些问题，一时之间学不会也没事，看多了就学会了，不信？继续往下看，下面的这几道题，也是非常常见的，可能你之前也都做过。

3、找出没有重复的数

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。

这道题可能很多人会用一个哈希表来存储，每次存储的时候，记录 某个数出现的次数，最后再遍历哈希表，看看哪个数只出现了一次。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)了。

然而我想告诉你的是，采用位运算来做，绝对高逼格！

我们刚才说过，两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身，所以我们把这一组整型全部异或一下，例如这组数据是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出现了一次，其他都出现了两次，把他们全部异或一下，结果如下：

由于异或支持交换律和结合律，所以:

1²3⁴5¹2³4 = （1¹⁾(2²⁾(3³⁾(4⁴⁾5= 0⁰0⁰5 = 5。

也就是说，那些出现了两次的数异或之后会变成0，那个出现一次的数，和 0 异或之后就等于它本身。就问这个解法牛不牛逼？所以代码如下

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

时间复杂度为 O(n)，空间复杂度为 O(1)，而且看起来很牛逼。

4、m的n次方

如果让你求解 m 的 n 次方，并且不能使用系统自带的 pow 函数，你会怎么做呢？这还不简单，连续让 n 个 m 相乘就行了，代码如下：

int pow(int n){
    int tmp = 1;
    for(int i = 1; i <= n; i++) {
        tmp = tmp * m;
    }
    return tmp;
}

不过你要是这样做的话，我只能呵呵，时间复杂度为 O(n) 了，怕是小学生都会！如果让你用位运算来做，你会怎么做呢？

我举个例子吧，例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:

m^1101 = m^0001 * m^0100 * m^1000。

我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。直接看代码吧，反而容易理解：

int pow(int n){
    int sum = 1;
    int tmp = m;
    while(n != 0){
        if(n & 1 == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }
    
    return sum;
}

时间复杂度近为 O(logn)，而且看起来很牛逼。

这里说一下，位运算很多情况下都是很二进制扯上关系的，所以我们要判断是否是否位运算，很多情况下都会把他们拆分成二进制，然后观察特性，或者就是利用与，或，异或的特性来观察，总之，我觉得多看一些例子，加上自己多动手，就比较容易上手了。所以呢，继续往下看，注意，先别看答案，先看看自己会不会做。

5、找出不大于N的最大的2的幂指数

传统的做法就是让 1 不断着乘以 2，代码如下：

int findN(int N){
    int sum = 1;
   while(true){
        if(sum * 2 > N){
            return sum;
        }
        sum = sum * 2;
   }
}

这样做的话，时间复杂度是 O(logn)，那如果改成位运算，该怎么做呢？我刚才说了，如果要弄成位运算的方式，很多时候我们把某个数拆成二进制，然后看看有哪些发现。这里我举个例子吧。

例如 N = 19，那么转换成二进制就是 00010011（这里为了方便，我采用8位的二进制来表示）。那么我们要找的数就是，把二进制中最左边的 1 保留，后面的 1 全部变为 0。即我们的目标数是 00010000。那么如何获得这个数呢？相应解法如下：

1、找到最左边的 1，然后把它右边的所有 0 变成 1

2、把得到的数值加 1，可以得到 00100000即 00011111 + 1 = 00100000。

3、把 得到的 00100000 向右移动一位，即可得到 00010000，即 00100000 >> 1 = 00010000。

那么问题来了，第一步中把最左边 1 中后面的 0 转化为 1 该怎么弄呢？我先给出代码再解释吧。下面这段代码就可以把最左边 1 中后面的 0 全部转化为 1，

n |= n >> 1;
n |= n >> 2;
n |= n >> 4;

就是通过把 n 右移并且做或运算即可得到。我解释下吧，我们假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后，那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算，那么得到的结果中第 k 和 第 k + 1 位必定是 1;同样的道理，再次把 n 右移两位，那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算，那么就能得到第 k, k+1, k+2, k+3 都是 1，如此往复下去…

最终的代码如下

int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。
    return (n + 1) >> 1;
}

这种做法的时间复杂度近似 O(1)，重点是，高逼格。

总结

上面讲了 5 道题，本来想写十道的，发现五道就已经写了好久了，，，，十道的话，怕你们也没耐心写完，而且一道比一道难的那种，，，，。

不过呢，我给出的这些例子中，并不是让你们学会了这些题就 Ok，而且让你们有一个意识：很多时候，位运算是个不错的选择，至少时间效率会快很多，而且高逼格，装逼必备。所以呢，以后可以多尝试去使用位运算哦，以后我会再给大家找些题来讲讲，遇到高逼格的，感觉很不错的，就会拿来供大家学习了。

兄dei，如果觉得我写的不错，不妨帮个忙

1、关注我的原创微信公众号「帅地玩编程」，每天准时推送干货技术文章，专注于写算法 + 计算机基础知识（计算机网络+ 操作系统+数据库+Linux），听说关注了的不优秀也会变得优秀哦。

2、给俺点个赞呗，可以让更多的人看到这篇文章，顺便激励下我，嘻嘻。

作者简洁

作者：大家好，我是帅地，从大学、自学一路走来，深知算法，计算机基础知识的重要性，所以申请了一个微星公众号『帅地玩编程』，专业于写这些底层知识，提升我们的内功，帅地期待你的关注，和我一起学习。 转载说明：未获得授权，禁止转载