C++ Leetcode 每日一题 Gray Code 位运算 数学

Leetcode每日一题 格雷编码

每日一题

Posted by 物联黄同学 on January 8, 2022

2022-1-8 Leetcode每日一题 格雷编码

打打每日一题，顺便拓宽知识面了解什么是Gray Code

一. Gray Code 背景知识

参考：Gray Code的百度百科

1. 什么是格雷码

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。 [2] 在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。

3个点：

  1. 相邻代码的二进制数只有1位不同
  2. 最大数与最小数也是只有1位不同，“首尾相连”
  3. 因为除第一个每一个代码相比前一个的变化的变化小，只有1位二进制位，适用于数字系统

2. 提出者

弗兰克-格雷

Frank Gray

3. 特点

  • 格雷码属于可靠性编码，是一种错误最小化的编码方式。因为，虽然自然二进制码可以直接由数/模转换器转换成模拟信号，但在某些情况，例如从十进制的3转换为4时二进制码的每一位都要变，能使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点，它在相邻位间转换时，只有一位产生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。由于这种编码相邻的两个码组之间只有一位不同，因而在用于方向的转角位移量－数字量的转换中，当方向的转角位移量发生微小变化（而可能引起数字量发生变化时，格雷码仅改变一位，这样与其它编码同时改变两位或多位的情况相比更为可靠，即可减少出错的可能性。
  • 格雷码是一种绝对编码方式，典型格雷码是一种具有反射特性和循环特性的单步自补码，它的循环、单步特性消除了随机取数时出现重大误差的可能，它的反射、自补特性使得求反非常方便。
  • 由于格雷码是一种变权码，每一位码没有固定的大小，很难直接进行比较大小和算术运算，也不能直接转换成液位信号，要经过一次码变换，变成自然二进制码，再由上位机读取。 [3]
  • 典型格雷码是一种采用绝对编码方式的准权码，其权的绝对值为2^i-1(设最低位i=1)。
  • 格雷码的十进制数奇偶性与其码字中1的个数的奇偶性相同。

总结：

  1. 错误最小胡，大大减小了由一个状态到另一个状态时的混淆
  2. 绝对编码方式，循环、单步消除了随机取数时出现重大误差，反射、自补使得求反方便
  3. 变权码
  4. 其十进制数奇偶性与其字段（二进制）1的个数的奇偶性相同

4. 应用

  1. 角度传感器
  2. 格雷码
  3. 九连环问题
  4. 当初是为了通信，现在则常用于模拟－数字转换和位置

二、题目

题目链接

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中： 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1） 第一个整数是 0 一个整数在序列中出现 不超过一次 每对 相邻 整数的二进制表示 恰好一位不同 ，且 第一个 和 最后一个 整数的二进制表示 恰好一位不同 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

题目示例

7P3vXF.png

范围

1<= n <= 16

三、题解

参考官方题解

方案一 对称生成

代码如下

class Solution
{
public:
	/// <summary> 总结
	/// 思路
	/// 对称生成
	/// 1.假设n-1位的Gray Code 为 Gn-1
	/// 2.将Gn-1对称翻转 记为 T(Gn-1)，这样Gn-1 的首元素 和 T(Gn-1) 的尾元素相同
	/// 3.如果T(Gn-1)的每个元素 加上 1 << n - 1, 即为T(Gn-1)'
	/// 4.则Gn-1 的首元素和 T(Gn-1)'的尾元素只有一位不同，反之亦然
	/// 所以
	/// Gn = {Gn-1, T(Gn-1)'}
	/// </summary>
	/// <param name="n"> 参数n
	/// 表示要返回格雷码最大元素二进制长度元素
	/// 即要返回一个长度位 2的n次方长度 的格雷序列
	/// </param>
	/// <returns>
	/// 返回一个格雷序列
	/// </returns>
	vector<int> grayCode(int n)
	{
		vector<int> ret;
		// reserve函数， 改变vector的capacity，但是和resize不同的是，reserve使用后
		// 不能直接使用或者引用相关元素，即使是添加相关元素时也需要insert或者push_back
		ret.reserve(1 << n);
		ret.push_back(0);
		for (int i = 1; i <= n; ++i)
		{
			// 可以看到使用reserve并没有改变ret的size
			int m = ret.size();
			//cout << m << endl;
			// 循环对称生成当前层次的 T(Gi-1)'
			for (int j = m - 1; j >= 0; --j)
			{
				ret.push_back(ret[j] | (1 << (i - 1)));
			}
		}
		return ret;
	}
};

方案二 数学位运算

class Solution
{
public:
	/// <summary>
	/// 二进制数字转格雷码
	/// 假设n位二进制数字b，对应的格雷码为g
	/// g(i)=b(i+1)⊕b(i),    0≤i<n， 且b(n)= 0
	/// 算法证明
	/// 1. bi+1 = bi + 1, 会把bi的末位连接的1全部变成0，而最低位的0则置1
	/// 2. 按照二进制转格雷码的规则，假设涉及到转换的二进制位数位有k位
	/// 3. 得到的gi 和 gi+1 只有在第 k - 1位不同，所以相邻元素只有1位不同
	/// 4. 而格雷序列第一位和最后一位分别由0和的2的n次方-1转换而来，也只有1位不同
	/// 5. 又由于这种转换为 一对一映射，不存在转换得到相同元素
	/// </summary>
	/// <param name="n">
	/// </param>
	/// <returns></returns>
	vector<int> grayCode(int n)
	{
		vector<int> ans(1 << n);
		for (int i = 0; i < ans.size(); ++i)
		{
			// 二进制数转Gary Code
			ans[i] = (i >> 1) ^ i;
		}
		return ans;
	}
};

后话

溜了，去复习线代和信安了，不能摆烂了！！！

CATALOG
    FRIENDS