Table of Contents
Algorithm
Leetcode 1234: Replace the Substring for Balanced String
https://dreamume.medium.com/leetcode-1234-replace-the-substring-for-balanced-string-9885b4a64adf
Review
访问控制从代码中在其他源文件和模块中限制访问你的代码部分。这个特性使得你隐藏你代码的实现细节,且指定一个更好的接口让代码访问和使用
你可赋值特别的访问层级到私有类型(类、结构和枚举),和属于这些类型的属性、方法、初始化函数和下标。协议可限制到某个上下文,可为全局常量、变量和函数
另外提供各种访问控制层级,Swift 通过提供类型场景的默认访问层级来缩减直接指明访问控制层级的需要。事实上,如果你写单个 app,你可完全不需要指明访问控制层级
模块、源文件和包
Swift 的访问控制模型基于模块、源代码和包的概念
一个模块是代码分发的一个单元 - 一个 framework 或应用程序且可用 Swift 的 import 关键字在其他模块导入
在 Xcode 中每个构建目标在 Swift 被作为一个独立模块处理。如果你收集你的应用程序代码作为一个独立 framework - 也许跨多个应用程序封装和重用代码 - 则 framework 里你定义的所有将为一个独立模块的一部分当它导入并使用在一个 app 中时,或被另一个 framework 使用
一个源文件是一个模块里的一个 Swift 源代码文件。虽然通常在独自的源文件中定义独立的类型,一个源文件可包含多个类型、函数等的定义
一个包是你开发的一组模块作为一个单元。你定义模块作为你使用的配置构建系统的一部分,而不是你 Swift 源代码的一部分。例如,如果你使用 Swift 包管理器构建你的代码,你在你的 Package.swift 文件里定义一个包使用 PackageDescription 模块里的 API,且如果你使用 Xcode,你在包访问唯一标识符构建设置里指明包名称
访问层级
Swift 对你的代码提供六种不同的访问层级。这些访问层级对条目定义的源文件,源文件所属的模块和模块所属的包相关
- open 访问和 public 访问使在条目定义的模块中的任意源文件和导入该定义模块其他模块源文件可以使用该条目。典型地你在指明一个公共接口到库时使用 open 或 public 访问
- 包访问使得条目用于定义它们的包里的任意源文件,其他包源文件则不允许。你典型地在 app 或结构化为多个模块的库中使用包访问
- 内部访问使条目用于定义它们的模块的任意源文件中,其他源文件则不允许。你典型地当定义一个 app 的或库的内部结构时使用内部访问
- 文件私有访问限制条目用于定义它的源文件里。使用文件私有访问隐藏一个特殊功能的细节实现,其细节用于整个文件
- 私有访问限制条目的使用在相同文件中相关定义域和定义扩展中。使用私有访问隐藏一个特殊功能的实现细节,其细节只用于单个定义中
open 访问是最高访问层级且私有访问是最低访问层级
open 访问只应用于类和类成员,且它跟公开访问不同,允许模块外的代码对其子类化和覆盖。标记一个类为 open 直接表示你考虑这个类作为父类在其他模块中的影响,且合理地设计你的类代码
访问层级的指导原则
在 Swift 中的访问层级遵循一个总的指导原则:没有条目可用另一个更低访问层级的条目定义
例如:
- 一个 public 变量不能有一个内部、文件私有或私有类型,因为类型可能不会在公开变量的任意位置有效
- 一个函数不能有比它的参数类型和返回类型更高的访问层级,因为函数可能用于当它的组成类型对周围代码无效的情况
这个指导原则的特别间接说明对语言的其他方面的具体细节在后续章节描述
缺省访问层级
你代码的所有条目当你不直接指定访问层级时有一个内部的缺省访问层级
单目标 app 的访问层级
当你写一个简单的单目标 app,你的程序代码典型地被 app 自包含且不需要在 app 模块外部有效。内部的缺省访问层级已经匹配这个需求。因此,你不需要指明一个自定义的访问层级。你可,想要标记你的代码的一些部分作为文件私有或私有来对 app 模块的其他代码隐藏它们的实现细节
库的访问层级
当你开发一个库,标记一个开放接口作为 open 或 public 这样它可被其他模块看到和访问,这样一个 app 可导入这个库。这样这个开放接口是库的应用程序编程接口
目标单元测试的访问层级
当你用一个单元测试目标写一个 app,你的 app 代码需要对该模块有效来测试。缺省,只有标记为 open 或 public 的条目可被其他模块访问。然而,一个单元测试目标可访问任意内部条目,如果你对一个产品模块用 @testable 属性标记导入定义并用测试启动属性来编译该产品模块
访问控制语法
通过在条目定义的开头摆放 open、public、internal、fileprivate 或 private 修饰符来定义一个条目的访问层级
open class SomeOpenClass {}
public class SomePublicClass {}
internal class SomeInternalClass {}
fileprivate class SomeFilePrivateClass {}
private class SomePrivateClass {}
open var someOpenVariable = 0
public var somePublicVariable = 0
internal let someInternalConstant = 0
fileprivate func someFilePrivateFunction() {}
private func somePrivateFunction() {}
除非已指定,缺省的访问层级是 internal。这意味着 SomeInternalClass 和 someInternalConstant 可不用直接指定访问层级修饰符,将会有 internal 的访问层级
class SomeInternalClass {} // implicitly internal
let someInternalConstant = 0 // implicitly internal
自定义类型
如果你想要对一个自定义类型指定一个访问层级,在定义它的时候指定。当新类型的访问层级允许时它就可用。例如,如果你定义一个 file-private 类,该类只能用于属性类型或函数参数或返回类型,在 file-private 类定义的文件中
一个类型的访问控制层级也影响该类成员(它的属性、方法、初始化函数和下标)的缺省访问层级。如果你定义一个类型的访问层级为 private 或 file private,它的成员的缺省访问层级将也为 private 或 file private。如果你定义一个类型的访问层级为 internal 或 public(或不直接指定一个访问层级使用 internal 的缺省访问层级),类型成员的缺省访问层级为 internal
重要:一个公开类型缺省有 internal 的成员,而不是 public 的成员。如果你想要一个类型成员为 public,你必须直接标记它为 public。这个需求确保一个类型的公开 API 是你选择发布的,且避免错误地呈现一个类型的内部工作作为公开接口
public class SomePublicClass { // explicitly public class
public var somePublicProperty = 0 // explicitly public class member
var someInternalProperty = 0 // implicitly internal class member
fileprivate func someFilePrivateMethod() {} // explicitly file-private class member
private func somePrivateMethod() {} // explicitly private class member
}
class SomeInternalClass { // implicitly internal class
var someInternalProperty = 0 // implicitly internal class member
fileprivate func someFilePrivateMethod() {} // explicitly file-private class member
private func somePrivateMethod() {} // explicitly private class member
}
fileprivate class SomeFilePrivateClass { // explicitly file-private class
func someFilePrivateMethod() {} // implicitly file-private class member
private func somePrivateMethod() {} // explicitly private class member
}
private class SomePrivateClass { // explicitly private class
func somePrivateMethod() {} // implicitly private class member
}
元组类型
对一个元组类型的访问层级是使用在该元组中所有类型里最受限的访问层级。例如,如果你从两个不同类型拼装一个元组,一个为 internal 访问层级另一个为 private 访问层级,则组合的元组类型访问层级将为 private
注意 元组类型没有像类、结构、枚举和函数那样独立的定义。一个元组类型的访问层级自动从构成元组类型的类型中确定,且不能直接指定
函数类型
一个函数类型的访问层级是函数参数和返回类型中最受限的访问层级。你必须直接指定访问层级作为函数的定义如果函数的计算访问层级不匹配缺省的上下文时
下面例子定义一个全局函数称为 someFunction(),没有对函数本身提供一个指定的访问层级修饰符。你可期望这个函数有 internal 的缺省访问层级,但并不是。事实上,someFunction() 不会通过编译
func somefunction() -> (SomeInternalClass, SomePrivateClass) {
// function implementation goes here
}
函数的返回值是一个元组类型由两个自定义类组成。一个类定义为 internal,另一个定义为 private。因此,复合元组类型总的访问层级是 private
因为函数的返回类型是 private,你必须标注函数的总访问层级为 private 到函数定义才有效
private func someFunction() -> (SomeInternalClass, SomePrivateClass) {
// function implementation goes here
}
用 public 或 internal 修饰符标注 someFunction() 的定义是无效的,因为 函数的 public 或 internal 用户不能合适地访问函数返回类型中的 private 类
枚举类型
一个枚举的独立值自动接受它们所属的枚举的相同的访问层级。你不能对一个独立枚举值指定一个不同的访问层级
在下面例子中,CompassPoint 枚举有一个直接的访问层级 public。枚举值 north、south、east 和 west 因此也有访问层级 public
public enum CompassPoint {
case north
case south
case east
case west
}
裸值和关联值
在枚举中定义的用于任意裸值或关联值的类型必须有一个访问层级至少跟枚举的访问层级一样高。例如,你不能使用一个 private 类型作为一个 internal 类型枚举的裸值类型
嵌套类型
一个嵌套类型的访问层级跟它包含的类型一样,除非包含类型是 public。嵌套类型在一个 public 类型中定义有一个 internal 的自动访问层级。如果你想要一个 public 的嵌套类型为公开有效,你必须直接声明嵌套类型为 public
子类化
你可子类化在当前访问上下文和定义在相同模块中的任意类作为子类。你可子类不同模块下任意 open 类。一个子类不能有比它的父类更高的访问层级 - 例如,你不能写一个 internal 父类的一个 public 子类
另外,对定义在相同模块的类,你可覆盖在某个访问上下文中可见的任意类成员(方法、属性、初始化函数或下标)。对定义在另一个模块中的类,你可覆盖任意 open 类成员
一个覆盖可使得一个继承类成员比它的父类版本更可访问。在下面例子中,类 A 是一个 public 类带一个 file-private 的方法称为 someMethod()。类 B 是类 A 的子类,带一个 internal 的访问层级。尽管,类 B 提供一个带 internal 访问层级的覆盖的 someMethod() 方法,其访问层级高于原始实现的 someMethod() 访问层级
public class A {
fileprivate func someMethod() {}
}
internal class B: A {
override internal func someMethod() {}
}
一个子类成员调用一个比子类成员访问层级小的父类成员也是有效的,调用父类成员发生在一个允许的访问层级上下文(在相同源代码下父类一个 file-private 成员调用,或在相同模块下父类一个 internal 成员调用):
public class A {
fileprivate func someMethod() {}
}
internal class B: A {
override internal func someMethod() {
super.someMethod()
}
}
因为父类 A 和子类 B 定义在相同的源代码文件中,对 B 的 someMethod() 实现调用父类的 super.someMethod() 方法是有效的
常量、变量、属性和下标
一个常量、变量或属性不能比它的类型更公开。写一个私有类型的 public 属性是无效的。相似的,一个下标不能比它的索引类型或返回类型更公开
如果一个常量、变量、属性或下标用一个私有类型,常量、变量、属性或下标必须也标注为私有
private var privateInstance = SomePrivateClass()
Getter 和 Setter
常量、变量、属性和下标的 Getter 和 Setter 自动收到属于它们的常量、变量、属性或下标的访问层级
你可给出一个 setter 比它对应的 getter 更低的访问层级,来限制变量、属性或下标的读写范围。你给定一个更低的访问层级通过写 fileprivate(set)、private(set)、internal(set) 或 package(set) 在 var 或 subscript 之前
注意 这个规则应用到存储属性也用于计算属性。甚至你不对一个存储属性直接写 getter 和 setter,Swift 仍会同步一个间接的 getter 和 setter 来提供访问存储属性背后的存储。使用 fileprivate(set)、private(set)、internal(set) 和 package(set) 来改变这个同步 setter 的访问层级,这在计算属性上也一样
下面例子定义一个结构称为 TrackedString,其保存 string 属性修改的次数:
struct TrackedString {
private(set) var numberOfEdits = 0
var value: String = "" {
didSet {
numberOfEdits += 1
}
}
}
TrackedString 结构定义一个存储字符串属性称为 value,初始值为 ““。结构也定义一个存储整型属性称为 numberOfEdits,用来跟踪 value 修改的次数。这个修改用 value 上的 didSet 属性观察者实现,在 value 属性设置一个新值时增一
TrackedString 结构和 value 属性不提供一个直接的访问层级修饰符,且这样它们都接收 internal 的缺省访问层级。然而,numberOfEdits 属性的访问层级用一个 private(set) 标注来表明属性的 getter 还是缺省的访问层级,但属性只在 TrackedString 结构代码里可修改。这使得 TrackedString 在内部修改 numberOfEdits 属性,但在结构定义之外呈现为只读属性
如果你创建一个 TrackedString 实例并修改它的 value 值几次,你可看到 numberOfEdits 属性值跟修改次数一样
var stringToEdit = TrackedString()
stringToEdit.value = "This string will be tracked."
stringToEdit.value += " This edit will increment numberOfEdits."
stringToEdit.value += " So will this one."
print("The number of edits is \(stringToEdit.numberOfEdits)")
// Prints "The number of edits is 3"
注意你可按需要对 getter 和 setter 设置一个直接的访问层级。下面例子显示一个 TrackedString 结构版本,该结构定义为指定的 public 访问层级。结构的成员因此有 internal 的默认访问层级。你可使结构的 numberOfEdits 属性 getter 为 public,且 setter 为 private,组合 public 和 private(set) 访问层级修饰符
public struct TrackedString {
public private(set) var numberOfEdits = 0
public var value: String = "" {
didSet {
numberOfEdits += 1
}
}
public init() {}
}
初始化函数
自定义初始化函数可被赋予一个访问层级小于或等于它们初始化的类型。唯一的例外是需求初始化函数。一个需求初始化函数必须有属于它的类的一样的访问层级
对于函数和方法参数,一个初始化函数的参数类型不能比初始化函数本身的访问层级更小
缺省初始化函数
Swift 对任意结构或基类自动提供一个没有任何参数的缺省初始化函数,其设置所有它的属性的初始值且不提供至少一个初始化函数
一个缺省初始化函数有它初始化类型相同的访问层级,除非类型定义为 public。对定义为 public 的类型,缺省初始化函数为 internal。如果你想要一个 public 类型
对结构类型的缺省成员初始化函数
结构类型的缺省成员初始化函数在任意结构的存储属性为 private 时其也为 private。同样的,如果任意结构的存储属性为 file private,则该初始化函数也为 file private。否则,该初始化函数为 internal
如果你想要在另一个模块里使用一个 public 的结构类型用成员初始化函数来初始化,你必须在类型的定义中提供一个 public 的成员初始化函数
协议
如果你想要给一个协议类型直接赋值一个访问层级,你要在协议定义的时候做。这使得你创建的协议只适配某种访问上下文
在一个协议里定义的每一个需求的访问层级自动设置为该协议相同的访问层级。你不能设置一个协议需求为不同于协议支持的其他访问层级。这确保所有协议的需求在任意适配协议的类型上都可见
注意 如果你定义一个 public 的协议,协议的需求当实现时需要一个 public 的访问层级。这个行为跟其他类型不同,其他类型的定义意味着对类型成员的间接的 internal 的访问层级
协议继承
如果你定义一个新协议继承自一个现存的协议,新协议最多有跟它继承的协议有相同的访问层级。例如,你不能写一个 public 的协议是从一个 internal 的协议继承的
协议遵从
一个类型可用比本身更低的访问层级遵从一个协议。例如,你可定义一个 public 的类型用于其他模块,其遵从一个 internal 的协议只能用在该协议定义的模块中
一个类型遵从一个特殊协议的上下文的访问层级是类型的访问层级和协议的访问层级的最小者。例如,如果一个类型是 public,但它遵从的一个协议是 internal,类型对该协议的遵从也是 internal
当你写或扩展一个类型遵从一个协议,你必须确保每个协议需求的类型的实现有至少跟类型遵从该协议相同的访问层级。例如,如果一个 public 的类型遵从一个 internal 协议,每个协议需求的类型的实现必须至少是 internal
注意 在 Swift 中,和 Objective-C 一样,协议遵从是全局的 - 它不能说一个类型在相同的程序中以两种不同的方式遵从一个协议
扩展
你可扩展一个类、结构或枚举在该类、结构或枚举有效的任意访问上下文中。添加到扩展中的任何类型成员有跟原始被扩展类型的类型成员有相同的缺省访问层级。如果你扩展一个 public 或 internal 类型,任何你添加的新的类型成员有一个缺省的 internal 的访问层级。如果你扩展一个 file-private 类型,你添加的任何新类型成员有一个 file-private 的缺省访问层级。如果你扩展一个 private 类型,你添加的任何新的类型成员将有一个 private 的默认访问层级
另外,你可用一个直接的访问层级修饰符标注一个扩展(例如,private)来设置定义在扩展中所有成员的一个新的默认访问层级。这个新的缺省可覆盖扩展的独立类型成员
如果你使用扩展来添加协议遵从,你不能给扩展提供一个直接的访问层级修饰符。而是,协议的自己的访问层级用来提供扩展中对每个协议需求实现的缺省访问层级
扩展中的 private 成员
扩展跟被扩展的类、结构或枚举在相同的文件中,就像扩展中的代码作为原始类型定义的一部分。结果,你可:
- 在原始声明中定义一个 private 成员,且在相同文件中扩展可访问该成员
- 在一个扩展中声明一个 private 成员,在相同文件中其他扩展可访问该成员
- 在一个扩展中声明一个 private 成员,在相同文件中从原始声明中访问该成员
这个行为意味着你可使用扩展组织你的代码,不管你的类型有 private 的条目。例如,给出下面的简单协议:
protocol SomeProtocol {
func doSomething()
}
你可使用扩展来添加协议遵从,如下:
struct SomeStruct {
private var privateVariable = 12
}
extension SomeStruct: SomeProtocol {
func doSomething() {
print(privateVariable)
}
}
范型
一个范型类型或范型函数的访问层级是范型类型或函数本身的访问层级和在它的类型参数上任意类型限制的访问层级的最小值
类型别名
任意你定义的类型别名因访问控制的原因作为一个不同的类型对待。一个类型别名可有其被别名的类型的相同或低于其的访问层级。例如,一个 private 类型别名可设置为 private、file-private、internal、public 或 open 类型,但一个 public 类型别名不能被 internal、file-private 或 private 类型的来别名
注意 这个规则也应用于用来满足协议遵从的关联类型的类型别名
Tips
Swift 提供了一些高级操作执行更加复杂的值操作。这些包括你在 C 或 Objective-C 中熟悉的位和位移操作
跟 C 的算数操作不同,Swift 中的算术操作缺省不溢出。溢出行为被设陷并报道为一个错误。要选择溢出行为,使用 Swift 的第二个集合的缺省算术操作,比如溢出加法操作(&+)。所有这些溢出操作以 & 符号开头
当你定义你自己的结构、类和枚举,对这些自定义类型提供你自己的标准 Swift 操作实现是很有用的。Swift 很容易提供这些操作的尾实现并精确决定对每个你创造的类型应该用什么行为
你不限制预定义操作,Swift 给你自由来定义你自己的自定义 infix、prefix、postfix 和赋值操作,用自定义的优先级和相关值。这些操作可用于适配在你的代码里跟任意预定义操作一样,且你可甚至扩展现存的类型来支持你定义的自定义操作
位操作
位操作使你在一个数据结构中操作独立的裸数据位。通常使用在底层编程中,比如图形编程和创建设备驱动。位操作在你从外部源中操作裸数据时也很有用,比如从一个自定义协议中编码和解码通信数据
Swift 支持所有 C 语言中的位操作
NOT 操作
NOT 操作是一个前置操作符,反转所有数字中的位
let initialBits: UInt8 = 0b00001111
let invertedBits = ~initialBits // equals 11110000
AND 操作
AND 操作组合两个数字的位
let firstSixBits: UInt8 = 0b11111100
let lastSixBits: UInt8 = 0b00111111
let middleFourBits = firstSixBits & lastSixBits // equals 00111100
OR 操作
OR 操作比较两个数字的位
let someBits: UInt8 = 0b10110010
let moreBits: UInt8 = 0b01011110
let combinedbits = someBits | moreBits // equals 11111110
XOR 操作
XOR 操作异或两个数字的位
let firstBits: UInt8 = 0b00010100
let otherBits: UInt8 = 0b00000101
let outputBits = firstBits ^ otherBits // equals 00010001
位左移和右移操作
-
无符号整数的移动操作
无符号整数的位移行为如下:
- 根据需求将现存的位左移或右移
- 移出超过整数存储边界的任意位被丢弃
-
左移或右移后空出来的位插入 0
let shiftBits: UInt8 = 4 // 00000100 in binary shiftBits « 1 // 00001000 shiftBits « 2 // 00010000 shiftBits « 5 // 10000000 shiftBits « 6 // 00000000 shiftBits » 2 // 00000001
-
有符号整数的移动行为
有符号整数使用第一个位(称为符号位)来表示整数为正还是负。一个符号位为 0 表示正,否则表示负
剩下的位(称为值位)存储实际的值。正数存储跟无符号一致
负数则不同,它们存储为用 2 的 n 次方减去它们的绝对值,n 是值位的个数
这种负数的编码被称为 2 的补码表示,它有几个优点
首先,两个负数相加可操作为所有位的标准二进制加法,并丢弃溢出位
其次,2 的补码表示法让你左移或右移操作时跟正数相同,而对于左移,有一个额外的规则,左移后空出来的位需要填 1
溢出操作
如果你尝试插入一个数到一个整型常量或变量而导致不能持有该值,Swift 默认会报道一个错误而不是允许一个非法的值创建。当你操作过大或过小的数时这个行为给了你额外的安全性
例如,Int16 整数类型持有的值范围为 -32768 到 32767。尝试设置超过这个范围将导致一个错误
var potentialOverflow = Int16.max
// potentialOverflow equals 32767, which is the maximum value an Int16 can hold
potentialOverflow += 1
// this causes an error
当编程边界值条件时提供错误处理使得你有更多的灵活性
然而,当你指明想要一个溢出条件来截断数的有效位时,你可选择这个行为而不是触发一个错误。Swift 提供三个算术溢出操作来在整数计算中选择溢出行为:
- 溢出加法(&+)
- 溢出减法(&-)
- 溢出乘法(&*)
操作符方法
类和结构可提供它们自己的现存操作符的实现
下面例子显示对一个自定义类型如何实现一个算术加法操作
struct Vector2D {
var x = 0.0, y = 0.0
}
extension Vector2D {
static func + (left: Vector2D, right: Vector2D) -> Vector2D {
return Vector2D(x: left.x + right.x, y: left.y + right.y)
}
}
let vector = Vector2D(x: 3.0, y: 1.0)
let anotherVector = Vector2D(x: 2.0, y: 4.0)
let combinedVector = vector + anotherVector
// combinedVector is a Vector2D instance with values of (5.0, 5.0)
前置和后置操作
下面例子显示了一个二进制前置操作的自定义实现
extension Vector2D {
static prefix func - (vector: Vector2D) -> Vector2D {
return Vector2D(x: -vector.x, y: -vector.y)
}
}
let positive = Vector2D(x: 3.0, y: 4.0)
let negative = -positive
// negative is a Vector2D instance with values of (-3.0, -4.0)
let alsoPositive = -negative
// alsoPositive is a Vector2D instance with values of (3.0, 4.0)
复合赋值操作
复合赋值操作组合赋值和另一个操作。例如,加法赋值操作(+=)组合加法和赋值操作为一个操作。你标记一个复合赋值的左输入参数类型为 inout,因为参数的值将被操作方法直接修改
下面例子实现了一个加法赋值操作
extension Vector2D {
static func += (left: inout Vector2D, right: Vector2D) {
left = left + right
}
}
var original = Vector2D(x: 1.0, y: 2.0)
let vectorToAdd = Vector2D(x: 3.0, y: 4.0)
original += vectorToAdd
// original now has values of (4.0, 6.0)
注意 不能覆盖默认的赋值操作。只有复合赋值操作可被覆盖。相似的,三元操作(a ? b : c)不能覆盖
相等操作
缺省,自定义类和结构没有相等操作实现。你通常实现 == 操作,并使用 Swift 的标准库 ! = 操作的缺省实现来获得 = = 操作的反向结果。有两种实现 = = 操作的方法:你可实现你自己的,或对多数类型,你可要求 Swift 同步一个实现给你。这两种情况下,你都要遵从 Swift 标准库的 Equatable 协议
你提供一个 == 操作符的实现跟实现其他前置操作符一样
extension Vector2D: Equatable {
static func == (left: Vector2D, right: Vector2D) -> Bool {
return (left.x == right.x) && (left.y == right.y)
}
}
let twoThree = Vector2D(x: 2.0, y: 3.0)
let anotherTwoThree = Vector2D(x: 2.0, y: 3.0)
if twoThree == anotherTwoThree {
print("These two vectors are equivalent.")
}
// Prints "These two vectors are equivalent."
自定义操作符
你可声明和实现你自己自定义的操作符附加到 Swift 提供的标准操作符
在全局声明的新操作符要使用 operator 关键字,且标记 prefix、infix 或 postfix 修饰符
prefix operator +++
extension Vector2D {
static prefix func +++ (vector: inout Vector2D) -> Vector2D {
vector += vector
return vector
}
}
var toBeDoubled = Vector2D(x: 1.0, y: 4.0)
let afterDoubling = +++toBeDoubled
// toBeDoubled now has values of (2.0, 8.0)
// afterDoubling also has values of (2.0, 8.0)
自定义 Infix 操作符的优先级
自定义 infix 操作符每个属于一个优先级组。一个优先级组指明一个操作符相对其他 infix 操作符的优先级,及操作的相关性
一个自定义 infix 操作符不能直接置于给定一个缺省优先级组其优先级高于三元条件操作符的优先级的优先级组中
下面例子定义一个新的自定义 infix 操作符 +-,其属于优先级组 AdditionPrecedence
infix operator +-: AdditionPrecedence
extension Vector2D {
static func +- (left: Vector2D, right: Vector2D) -> Vector2D {
return Vector2D(x: left.x + right.x, y: left.y - right.y)
}
}
let firstVector = Vector2D(x: 1.0, y: 2.0)
let secondVector = Vector2D(x: 3.0, y: 4.0)
let plusMinusVector = firstVector +- secondVector
// plusMinusVector is a Vector2D instance with values of (4.0, -2.0)
注意 你不能在定义一个 prefix 或 postfix 操作符时指定一个优先级。然而,如果你应用 prefix 和 postfix 操作符到同一个操作值上,postfix 操作符会先运行
结果构建器
一个结果构建器是一个你定义的类型,其添加创建嵌套数据的语法,比如一个列表或树,以一种自然声明式的方式。用在结果构建器中的代码可包含普通的 Swift 语法,比如 if 和 for,为处理条件和重复的数据片段
以下代码定义了一些类型来使用星和文本来画一条线
protocol Drawable {
func draw() -> String
}
struct Line: Drawable {
var elements: [Drawable]
func draw() -> String {
return elements.map { $0.draw() }.joined(separator: "")
}
}
struct Text: Drawable {
var content: String
init(_ content: String) { self.content = content }
func draw() -> String { return content }
}
struct Space: Drawable {
func draw() -> String { return " " }
}
struct Stars: Drawable {
var length: Int
func draw() -> String { return String(repeating: "*", count: length) }
}
struct AllCaps: Drawable {
var content: Drawable
func draw() -> String { return content.draw().uppercased() }
}
let name: String? = "Ravi Patel"
let manualDrawing = Line(elements: [
Stars(length: 3),
Text("Hello"),
Space(),
AllCaps(content: Text((name ?? "World") + "!")),
Stars(length: 2),
])
print(manualDrawing.draw())
// Prints "***Hello RAVI PATEL!**"
这个代码可以工作,但有一点不好的感觉。在 AllCaps 后深入嵌套比较晦涩。如果你需要包含 switch 或 for 循环来构建绘制的部分,则没有办法。一个结果构建器让你重写代码使得其更像 Swift 代码
为定义一个结果构建器,你写 @resultBuilder 属性到一个类型声明中。例如,下面代码定义一个结果构建器称为 DrawingBuilder,其让你使用一个声明式语法定义一个绘制
@resultBuilder
struct DrawingBuilder {
static func buildBlock(_ components: Drawable...) -> Drawable {
return Line(elements: components)
}
static func buildEither(first: Drawable) -> Drawable {
return first
}
static func buildEither(second: Drawable) -> Drawable {
return second
}
}
DrawingBuilder 结构定义这些方法实现结果构建器语法部分。buildBlock(_:) 方法添加对在代码块中写一系列线的支持。它组合该块中组件为一条线。buildEither(first:) 和 buildEither(second:) 方法添加对 if else 的支持
你可应用 @DrawingBuilder 属性到一个函数参数,其返回一个闭包传递到方法为结果构建器为闭包创建的值,例如:
func draw(@DrawingBuilder content: () -> Drawable) -> Drawable {
return content()
}
func caps(@DrawingBuilder content: () -> Drawable) -> Drawable {
return AllCaps(content: content())
}
func makeGreeting(for name: String? = nil) -> Drawable {
let greeting = draw {
Stars(length: 3)
Text("Hello")
Space()
caps {
if let name = name {
Text(name + "!")
} else {
Text("World!")
}
}
Stars(length: 2)
}
return greeting
}
let genericGreeting = makeGreeting()
print(genericGreeting.draw())
// Prints "***Hello WORLD!**"
let personalGreeting = makeGreeting(for: "Ravi Patel")
print(personalGreeting.draw())
// Prints "***Hello RAVI PATEL!**"
makeGreeting(for:) 函数带一个 name 参数和使用它来绘制一个私人的问候。draw(_ :) 和 caps(_ :) 函数都带一个闭包作为它们的参数,并标记 @DrawingBuilder 属性。当你调用这些函数,你使用 DrawingBuilder 定义的特殊的语法。Swift 转换一个绘制的声明式描述为一系列在 DrawingBuilder 上方法的调用来构建传递到函数参数上的值。例如,Swift 转换 caps(_ :) 的调用为如下代码:
let capsDrawing = caps {
let partialDrawing: Drawable
if let name = name {
let text = Text(name + "!")
partialDrawing = DrawingBuilder.buildEither(first: text)
} else {
let text = Text("World!")
partialDrawing = DrawingBuilder.buildEither(second: text)
}
return partialDrawing
}
Swift 转换 if else 块到调用 buildEither(first:) 和 buildEither(second:) 方法。虽然你在你的代码中不调用这些方法,显示的转换结果使得它更容易看到当你使用 DrawingBuilder 语法时 Swift 如何转换你的代码
为在特殊的绘制语法中添加写循环的支持,添加一个 buildArray(_ :) 方法
extension DrawingBuilder {
static func buildArray(_ components: [Drawable]) -> Drawable {
return Line(elements: components)
}
}
let manyStars = draw {
Text("Stars:")
for length in 1...3 {
Space()
Stars(length: length)
}
}
在上述代码中,for 循环创建了一个绘制数组,且 buildArray(_ :) 方法让该数组变成一个线
Share
反射二进制代码(RBC),也称为反射二进制(RB)或 在 Frank Gray 之后叫 Gray Code,是一个二进制数字系统的顺序使得两个相邻的值只有一个位不同
例如,十进制值 1 在二进制可以表示为 001 和 2 表示为 010。在 Gray code 中,这些值表示为 001 和 011。即,从 1 到 2 增加一个值只改变一个位,而不是 2 个
Gray code 广泛应用于从电子交换机中防止伪造的输出和在电子通信中加快错误矫正比如数字地面电视和一些电缆电视系统。在这些设备中 Gray code 的使用帮助简化逻辑操作和减少实际中的错误
功能
许多设备通过关闭和打开开关来显示位置。如果该设备使用自然二进制代码,3 和 4 的位置互相靠近但二进制表示的三个位数都不同
十进制 | 二进制 |
---|---|
… | … |
3 | 011 |
4 | 100 |
… | … |
自然二进制代码的问题是物理开关不是理想的:它不太像物理开关精确同步地改变状态。上面显示的两个状态间所有三个开关改变了状态。当所有正在改变的短暂期间,开关将读取一些虚假的位置。甚至没有键反弹,短暂期可能会是 011 - 001 - 101 - 100。当开关出现在位置 001 时,观察者不能说如果有真正的位置 1,或在两个其他位置之间的一个暂时状态。如果输出反馈给一个序列系统,可能通过组合逻辑,则序列系统可能存储一个错误值
这个问题可通过一次只改变一个开关解决,这样没有任何歧义的位置,代码为一个连续集合整数,或对每个环形列表成员,一个字符信号使得没有两个代码为确定的,且每两个相邻的代码只有一个信号不同。这些代码也称为单位距离,单距离,单步,monostrophic 或 syncopic 代码,相邻代码间的 Hamming 距离为 1
发明
原理上,对于给定字节长度有多种这样的代码,但 Gray code 是第一个应用到非负整数上的一个特殊的二进制代码,二进制反射 Gray code,或 BRGC。贝尔实验室研究员 George R.Stibitz 在 1941 年用一个专利保护的应用程序描述这样的一个代码,在 1943 年获得允许。Frank Gray 在他的 1947 年专利保护的应用程序中引入反射二进制代码的名称,标记该代码“还没有识别的名字“。他从事实中获得“可能通过一些反射系统从方便的二进制代码构建“
在 Gray code 的标准编码中,最低有效位有 2 个开 2 个关的重复范型;下一个位数是 4 个开 4 个关的范型;第 i 位是 $ 2^{i} $ 开 $ 2^{i} $ 关,其他位也是这样。四个位的版本显示如下:
十进制 | 二进制 | Gray |
---|---|---|
0 | 0000 | 0000 |
1 | 0001 | 0001 |
2 | 0010 | 0011 |
3 | 0011 | 0010 |
4 | 0100 | 0110 |
5 | 0101 | 0111 |
6 | 0110 | 0101 |
7 | 0111 | 0100 |
8 | 1000 | 1100 |
9 | 1001 | 1101 |
10 | 1010 | 1111 |
11 | 1011 | 1110 |
12 | 1100 | 1010 |
13 | 1101 | 1011 |
14 | 1110 | 1001 |
15 | 1111 | 1000 |
对十进制 15 代码滚动到 0 只需要改变一个开关。这被称为循环或邻接属性的代码
在现代数字通信中,Gray code 在错误矫正中扮演重要的角色。例如,在数字调制方案比如 QAM 其数据典型地转换 4 位或更多符号,信号的星座表排列为位范型被相邻的星座点只一位不同来转换。通过比较前向错误矫正能矫正单位错误,它可能让接收者矫正任意由一个星座点到邻接点区域的转换错误。这使得转换系统很少会被噪音污染
尽管是 Stibitz 在 Gray 之前描述了这个代码,反射二进制代码之后被其他人命名为 Gray。两个不同的 1953 年专利保护的应用程序使用 Gray code 作为反射二进制代码的替代名;其中之一也列出“最小错误码“ 和”循环排列代码“。一个 1954 年专利保护的应用程序用了“Bell 电话 Gray code“。其他的名字包括“循环二进制代码“,”循环进度代码“,“循环排列二进制“或“循环排列的二进制“
Gray code 有时候错误认为是 19 世纪电子设备发明人 Elisha Gray
历史和实际的应用程序
数学谜
反射二进制代码在变得对工程师熟知之前应用到数学谜
二进制反射 Gray code 可表示为经典的中国环谜的底层解决方案,French Louis Gros 1872 年描述的一个序列机械谜机制
它可作为解决方案指导汉诺塔问题,基于 French Edouard Lucas 1883 年的一个游戏。相似的,Bucharest 和 Klagenfurt 塔游戏配置为三进制和八进制 Gray code
Martin Gardner 在科学美国人他的 1972 年八月数学游戏栏目中写了一个流行的 Gray code 的报道
代码也形成在超立方体上的一个汉密尔顿循环,其每个位视为一个维度
电报代码
在 1975 年或 1876 年,当法国工程师 Emile Baudot 对他的打印电报系统从使用 6 位代码改为使用 5 位代码,他在他的打印机轮上使用一个反射二进制代码排序字母,且对元音只使用 3 位代码。元音和辅音以字母序排序,且其他符号适合地排位,5 位字符码被识别为一个反射二进制代码。这个代码变成熟知的 Baudot 代码,且用一个小的改变,最终在 1932 年作为国际电报第一号(ITA1, CCITT-1)采用
同时,1874 年德国奥地利人 Otto Schaffler 展示了在维也纳使用的另一种用 5 位反射二进制代码作为相同目的的打印电报
模拟到数字信号转换
Frank Gray 因发明信号方法用来兼容彩色电视而闻名,他使用基于真空管道的一套设备发明了一种转换模拟信号到反射二进制代码组的方法。在 1947 年形成文件,该方法和设备在 1953 年获得专利权,且 Gray 的名字联系到了该代码。Gray 享有专利权的“PCM 管道“设备被贝尔实验室的 Raymond W. Sears 制作了出来。他跟 Gray 和 William M.Goodall 一起工作,他相信 Gray 在反射二进制代码上的想法
Gray 在转换模拟信号到数字信号上使用代码最小化错误上最感兴趣;他的代码在今天依然在用于这个目的
位置编码器
Gray code 相对于权重二进制编码更适合于线性和旋转位置编码器(绝对编码器和相位编码器)。这避免了当一个位置在二进制表达中多个位改变时会导致变化过程中的误读
例如,一些旋转编码器提供一个磁盘其在同心环上有电子传导 Gray code 范型。每个 track 有一个停滞的金属簧接触器提供到传导代码范型的电子接触。这些接触器一起以 Gray code 的形式产生输出信号。其他的编码器基于光纤或电磁传感器使用非接触机制产生 Gray code 输出信号
不管一个移动的编码器的机制或精度,位置测量错误可能在一些特殊位置上发生(代码边界)因为代码在它读取的特别时刻可能会改变。一个二进制输出代码可能因为在相同时刻不能使所有位改变而引起严重的位置测量错误。如果,在位置采样的时刻,一些位已改变而另一些没有,采样的位置将是不正确的。在绝对编码器中,显示位置可能远离实际的位置,且在递增编码器中,这会导致位置跟踪崩溃
相反地,位置编码器使用的 Gray code 确保任意两个连续位置的代码只有一位不同,即一个时刻只能改变一位。这样,最大位置错误将很小,显示一个位置邻接实际的位置
基因算法
由于 Gray code 的 Hamming 距离属性,它们有时使用在基因算法中。在这个领域它们非常有用,因为代码的修改允许多数时递增改变,但偶尔单个位改变可引起一个大的倾斜并导致一个新的属性
布尔电路最小化
Gray code 也用于从 1953 年开始的标签 Karnaugh 地图裁剪和 1958 年开始的 Handler 环图,这两个都是逻辑电路最小化的图像方法
错误矫正
在现代数字通信中,在应用一个错误错误矫正之前 1 维和 2 维 Gray code 在错误防止方面扮演一个重要的角色。例如,在数字调制方案比如 QAM 中数据典型地以 4 位或更多来传输,信号的星座图被排列这样位范型被邻接星座点只以一位之差覆盖。通过与能够矫正一位错误的前向错误矫正比较,对一个接收器它能够矫正导致一个星座点偏离到邻接点区域的任意传输错误。这使得传输系统不容易被噪音干扰
时钟域间的通信
数字逻辑设计师使用 Gray code 扩展通过多位统计信息同步不同时钟频率间的逻辑操作。逻辑考虑在不同时钟域上操作。它是许多不同时钟频率上操作设计大型芯片的基础
最小影响的通过状态循环
如果一个系统需要通过所有可能开关状态的一些控制组合来顺序循环,且控制的改变需要很小的花费(例如,时间、线、人工操作),一个 Gray code 最小化设置改变数来对每个状态组合只改变一个。一个例子为测试一个管道系统所有它的手工操作阀设置的组合
一个平衡 Gray code 可被构造,翻转每位相等的次数。因为位翻转分布均匀,这用下面方法优化:平衡 Gray code 最小化每个位位翻转的最大统计数
-
Gray code 统计和算术
George R. Stibitz 在 1941 年已经在一个二进制脉冲统计设备里利用一个反射二进制代码
一个典型 Gray code 统计的使用是构建一个 FIFO 数据缓冲读写存在不同时钟域的端口。在这样一个双端口 FIFO 里的输入输出统计使用 Gray code 防止捕获的跨时钟域无效临时状态。当改变时更新的读写指针需要在时钟域间传递,为能跟踪每个域 FIFO 的空和满状态。指针的每个位在这个时钟域传输中是非确定性采样。这样对每个位,要么旧值要么新值被广播。因此,如果在多位指针中多个位在采样点改变,一个错误的二进制值会被广播。通过确保只改变一个位,Gray code 保证只有可能采样值为新值或旧值。典型的用 2 的指数长度的 Gray code
有时电子系统中的数字总线用来传递一个时刻只增长或减少一个的数量,例如时钟域或一个数字模拟转换器中传递的一个事件统计输出。在这些应用程序中 Gray code 的优点是许多线广播延迟的不同呈现的代码位不能导致接收值通过超出 Gray code 顺序的状态。这个跟机械编码器构建的 Gray code 的优势相似,然而 Gray code 的源在这个例子中是一个电子统计器。统计器本身必须在 Gray code 中统计,否则如果统计器以二进制运行则统计器的输出值必须重新时钟化在它被转换为 Gray code 之后,因为当一个值从二进制转换成 Gray code,它可能在二进制数据位成为二进制到 Gray 转换电路的到达时刻不同即代码会短暂出现无序的状态。在电路转换统计值到 Gray code 之后增加一个时钟注册器可能引入一个时钟循环延迟,这样在 Gray code 中直接统计会更有利
为产生 Gray code 统计器中的下一个统计值,它需要有一些组合逻辑增加存储的当前统计值。一个方法是增加一个 Gray code 号转换它为普通二进制代码,对一个标准二进制增加器加一,且然后转换结果为 Gray code。Gray code 统计的其他方法在 Robert W. Doran 的报告中讨论,包括在一个二进制波动统计器中从第一个主从翻转门阀中获取输出
-
Gray code 地址
当编程代码执行时典型地导致一个本地连续地址的指令内存访问范型,使用 Gray code 地址而不是二进制地址的总线编码可减少地址位状态改变的数量,因此在一些低电力设计中减少 CPU 能量消耗
构建一个 n 位 Gray code
n 位二进制反射 Gray code 可通过反射列表(例如,以倒序列出条目)从 n - 1 位列表中递归产生,用一个二进制 0 前置在源列表之前,用二进制 1 前置在反射列表条目之前,然后用倒序串联源列表,例如,从 n = 2 列表中产生 n = 3 列表:
2 位列表 | 00, 01, 11, 10 |
反射 | 10, 11, 01, 00 |
用 0 前置旧条目 | 000, 001, 011, 010 |
用 0 前置新条目 | 110, 111, 101, 100 |
串联 | 000, 001 011, 010, 110, 111, 101, 100 |
1 位 Gray code 是 $ G_ {1} = (0, 1) $。这可认为从一个 0 位 Gray code 包含一个 0 长度单条目 $ G_ {0} = ( \land ) $ 递归构建出来。这个从 $ G_ {n} $ 产生 $ G_ {n+1} $ 的迭代过程使得标准反射代码的如下属性更清晰:
- $ G_ {n} $ 是数 $ 0, \ldots, 2^{n} - 1 $ 的一个排列(每个数在列表中只出现一次)
- $ G_ {n} $ 内嵌在 $ G_ {n+1} $ 的前半段
- 因此,编码是稳定的,一旦一个二进制数出现在 $ G_ {n} $ 中它出现在所有更长列表的相同位置;这样谈论可反射 Gray code 值 G(m) = 第 m 个反射 Gray code,从 0 开始计数
- $ G_ {n} $ 中每个条目跟之前的条目只有一位不同(Hamming 距离为 1)
- $ G_ {n} $ 中最后的条目跟第一个条目只有一位不同(代码可循环)
这些特性建议一个简单和快速的方法转换二进制值到对应的 Gray code。如果输入值的下一个更高位设置为 1 则每位被倒置。如果有效这可通过位移和异或操作平行处理:第 n 位 Gray code 通过计算 $ n \oplus \lfloor \frac{n}{2} \rfloor $ 来获得。前置一个 0 位代码顺序不变,前置一个 1 位反转代码顺序。如果在 i 位被倒置,邻居第 $ 2^{i} $ 块的顺序是反转的。例如,如果在 3 位代码序中 0 位被倒置,两个邻接代码序被反转
$ 000, 001, 010, 011, 100, 101, 110, 111 \to 001,000,011,010,101,100,111,110 $ (倒置 0 位)
如果第 1 位倒置,2 个代码块改变顺序:
$ 000,001,010,011,100,101,110,111 \to 010,011,000,001,110,111,100,101 $ (倒置第 1 位)
如果第 2 位倒置,4 个代码块反转顺序:
$ 000,001,010,011,100,101,110,111 \to 100,101,110,111,000,001,010,011 $ (倒置第 2 位)
这样,在位置 i 对位 $ b_ {i} $ 执行一个异或及在位置 i + 1 如果 $ b_ {i+1} = 0 $ 则对顺序不动,如果 $ b_ {i+1} = 1 $ 则反转 $ 2^{i+1} $ 代码块顺序。现在,这跟反射并前置方法产生 Gray code 的操作完全一致
一个相似的方法可用来反转转换,但每位的计算依赖下一个高位的计算值这样它不能并行执行。假设 $ g_ {i} $ 是第 i 个 Gray code 位($ g_ {0} $ 是最低位),且 $ b_ {i} $ 是第 i 个二进制代码位($ b_ {0} $ 是最低位),反转转换可递归给出:$ b_ {0} = g_ {0} $ 且 $ b_ {i} = g_ {i} \oplus b_ {i-1} $。另外,解码一个 Gray code 为一个二进制数可描述为在 Gray code 里位的一个前置和,在前置和中每个单独的累加操作用 2 取模
为迭代构建二进制反射 Gray code,在第 0 步用 $ code_ {0} = 0 $ 开始,且在第 i > 0 步找到 i 的二进制表示中最小位为 1 的位置且在之前的 $ code_ {i-1} $ 代码中在该位置翻转位来产生下一个代码 $ code_ {i} $
转换成 Gray code 和从 Gray code 转换
下面 C 函数从二进制代数和它们相关的 Gray code 之间进行转换。然而似乎有一次需要一位被处理的 Gray 到二进制的更快版本算法存在
typedef unsigned int uint;
/* This function converts an unsigned binary number to reflected binary Gray code. */
uint BinaryToGray(uint num) {
return num ^ (num >> 1);
}
/* This function converts a reflected binary Gray code number to a binary number */
uint GrayToBinary(uint num) {
uint mask = num;
while (mask) {
mask >>= 1; /* Each Gray code bit is exclusive-ored while all more significant bits */
num ^= mask;
}
return num;
}
/* A more efficient version for Gray codes 32 bits or fewer through the use of SWAR
(SIMD within a register) techniques.
It implements a parallel prefix XOR function. The assignment statements can be in any order.
This function can be adapted for longer Gray codes by adding steps */
uint GrayToBinary32(uint num) {
num ^= num >> 16;
num ^= num >> 8;
num ^= num >> 4;
num ^= num >> 2;
num ^= num >> 1;
return num;
}
/* A Four-bit-at-once variant changes a binary number (abcd)2 to (abcd)2 ^ (00ab)2,
then to (abcd)2 ^ (00ab)2 ^ (0abc)2 ^ (000a)2.*/
在更新的处理器上,在解码步骤里 ALU 指令数可通过 CLMUL 指令集缩减。如果 MASK 是以一个单零数字结尾的字符为 1 的常量二进制字符串,则带灰编码的 x 用 MASK 非进位乘法将总是得到 x 或它的位对立值
Gray code 的特殊类型
在实际中,”Gray code” 总是指二进制反射 Gray code(BRGC)。然而,数学家发现了其他类型的 Gray code。像 BRGC,每个包含字节的列表,每个字节跟下一个只相差一个位(Hamming 距离为 1)
n 位 Gray code 且长度小于 $ 2^{n} $
构建 n 位二进制 Gray code 且长度小于 $ 2^{n} $,如果长度为偶数。一个可能性是用一个平衡 Gray code 开始且移除开始和结尾的值对,或在中间的。OEIS sequence A290772 给出长度为 2n 包括 0 和使用最小位数的可能的 Gray 序列
n 进制 Gray code
有许多不同于二进制反射 Gray code 的特殊类型 Gray code。其中之一为 n 进制 Gray code,也被称为非布尔 Gray code。如名称所示,这种类型 Gray code 在编码中使用非布尔值
例如,一个 3 进制 Gray code 使用值 0,1,2。(n, k) Gray code 是 k 位 n 进制 Gray code。(3,2) Gray code 元素序列为:00,01,02,12,11,10,20,21,22。(n,k) Gray code 可递归构建,跟 BRGC 相似,或可迭代构建。一个迭代产生 (N, k) Gray code 的算法如下:
/* inputs: base, digits, value
output: Gray
Convert a value to a Gray code with the given base and digits.
Iterating through a sequence of values would result in a sequence
of Gray code in which only one digit changes at a time */
void toGray(unsigned base, unsigned digits, unsigned value, unsigned gray[digits]) {
unsigned baseN[digits]; /* store the ordinary base-N number, one digit per entry */
unsigned i; /* The loop variable */
/* Put the normal baseN number into the baseN array. For base 10, 109 would
be stored as [9, 0, 1] */
for (i = 0; i < digits; ++i) {
baseN[i] = value % base;
value = value / base;
}
/* Convert the normal baseN number into the Gray code equivalent.
Note that
the loop starts at the most significant digit and goes down */
unsigned shift = 0;
while (i--) {
/* The Gray digit gets shifted down by the sum of the higher digits */
gray[i] = (baseN[i] + shift) % base;
shift = shift + base - gray[i]; /* Subtrace from base so shift is possible */
}
}
// EXAMPLES
// input: value = 1899, base = 10, digits = 4
// output: baseN[] = [9,9,8,1], gray[] = [0,1,7,1]
// input: value = 1900, base = 10, digits = 4
// output: baseN[] = [0,0,9,1], gray[] = [0,1,8,1]
有一些其他的 (n, k) Gray code 的算法。从上述算法中产生的 (n, k) Gray code 也是循环的;一些算法,比如 Guan 的算法,当 k 为奇数时缺少这个属性。另一方面,这个方法一个时刻只改变一位数字,它可改变封装的值(从 n - 1 到 0 的循环)。在 Guan 的算法中,统计交替上升下降,这样两个 Gray code 之间的数字只有一位不同
Gray code 没有唯一的定义,因为这样的代码的一个列排列也是 Gray code。上述过程产生一个代码其降低低位数字,改变地越多,其更像一个正常的统计方法
看看 Skew 二进制数字系统,一个变种三进制数字系统其每次增加最多改变两个数字,每次增加可最多一个数字进位操作完成
平衡 Gray code
虽然二进制反射 Gray code 在很多场景下很有用,但在某些场景下不是最优的因为缺少“均匀”。在平衡 Cray code 中,不同坐标位置数值的改变尽可能接近。为使这更精确,设 G 为一个 R 进制完全 Gray 循环有转换序列 $ (\delta_ {k}) $;G 的转换统计(光谱)为整数的收集定义为
$ \lambda_ {k} = | { j \in \mathbb{Z}_ {R^{n}} : \delta_ {j} = k } |, \text{for} \quad k \in \mathbb{Z}_ {n} $
一个 Gray code 是均匀或均匀平衡的如果它的转换统计也是所有相等的,$ \forall k, \lambda_ {k} = \frac{R^{n}}{n} $。明显的,当 R = 2 时,只有 n 是 2 的指数倍时这样的代码才存在。否则,它可能可构建一个似平衡二进制代码,其两个转换统计之间最多只有 2 处不同;这样(组合两种情况)每个转换要么 $ 2 \lfloor \frac{2^{n}}{2n} \rfloor $ 或 $ 2 \lceil \frac{2^{n}}{2n} \rceil $。Gray code 也称为幂平衡如果所有它的转换统计相邻 2 的指数个,且这样的代码对每个 2 的指数都存在
例如,一个平衡 4 位 Gray code 有 16 个转换,可被均匀分布在所有四个位置(每个位置四个转换),使得它均匀平衡:
$ \begin{array}{llllllllllllllll} 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} \\ 0 & 0 & \color{red}{1} & 1 & 1 & 1 & \color{red}{0} & 0 & \color{red}{1} & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & \color{red}{1} & 1 & 1 & \color{red}{0} & 0 \\ \color{red}{0} & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 \end{array} $
一个 5 位平衡 Gray code 有总共 32 个转换,其不能均匀分布在位置上。在这个例子中,4 个位置每个有 6 个转换,且有一个位置有 8 个:
$ \begin{array}{llllllllllllllllllllllllllllllll} \color{red}{1} & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} & 0 & 0 \\ 1 & 1 & \color{red}{0} & 0 & \color{red}{1} & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & \color{red}{0} & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & \color{red}{1} & 1 \\ 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & \color{red}{1} \\ 1 & 1 & 1 & 1 & 1 & 1 & \color{red}{0} & 0 & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{1} & 1 & \color{red}{0} & 0 & 0 & \color{red}{1} & 1 & 1 & 1 & 1 & 1 \end{array} $
我们将展示一个似平衡二进制 Gray code 的构建和实现,其允许我们对每个 n 产生一个 n 位平衡 Gray code。主要原理是归纳构建一个 (n + 2) 位 Gray code $ G^{\prime} $ 给定一个 n 位 Gray code G 使得平衡属性被保留。为此,我们考虑分区 $ G = g_ {0}, \ldots, g_ {2^{n} - 1} $ 为偶数 L 个非空块,形如:
$ { g_ {0} }, {g_ {1}, \ldots, g_ {k_ {2}} }, {g_ {k_ {2} + 1}, \ldots, g_ {k_ {3}} }, \ldots, { g_ {k_ {L-2}+1}, \ldots, g_ {-2} }, { g_ {-1} } $
$ k_ {1} = 0, k_ {L-1} = -2, k_ {L} \equiv -1 \quad (mod \quad 2^{n}) $。这个分区引入一个 (n+2) 位 Gray code:
$ 00g_ { 0 }, $
$ 00g_ {1}, \ldots, 00g_ {k_ {2}}, 01g_ {k_ {2}}, \ldots, 01g_ {1}, 11g_ {1}, \ldots, 11g_ {k_ {2}}, $
$ 11g_ {k_ {2} + 1}, \ldots, 11g_ {k_ {3}}, 01g_ {k_ {3}}, \ldots, 01g_ {k_ {2} + 1}, 00g_ {k_ {2} +1}, \ldots, 00g_ {k_ {3}}, \ldots, $
$ 00g_ {-2}, 00g_ {-1}, 10g_{-1}, 10g_ {-2}, \ldots, 10g_ {0}, 11g_ {0}, 11g_ {-1}, 01g_ {-1}, 01g_ {0} $
如果我们定义转换重数
$ m_ {i} = | { j: \delta_ {k_ {j}} = i, 1 \le j \le L } | $
为在一个分区中连续块之间在数位 i 改变的次数,对 (n+2) 位 Gray code 通过这个分区谱 $ \lambda^{\prime}_ {i} $ 导入为
$ \lambda^{\prime}_ {i} = \left\{ \begin{array}{lc}4 \lambda_ {i}-2 m_ {i}, & \text { if } 0 \leq i < n \\ L, & \text { otherwise } \end{array} \right. $
这个构建的修饰部分为了找到一个 n 位 Gray code 的一个普适分区使得通过它引入的代码仍然是平衡的,但这只对转换重数有关;在一个位 i 转换连接两个相邻的块和在另一个 i 位上分隔块产生一个相同转换谱 $ \lambda^{\prime}_ {i} $ 上的不同的 Gray code,这样可以例如在位数 i 上指定第一个 $ m_ {i} $转换。均匀代码在 $ R \equiv 0 \quad (mod \, 4) $ 和 $ R^{n} \equiv 0 \quad (mod \, n) $ 上找到,且这个构建可扩展到 R 进制
长运行 Gray code
长运行(最大间隔)Gray code 最大化相同位置上连续改变数位的距离。即任何位的最小运行长度尽可能不改变
单调 Gray code
单调代码在互相连接网络上理论上很有用,特别对处理器的线性数列。如果我们定义一个二进制字符串的重量为字符串里 1 的个数,则虽然我们清楚 Gray code 不可能有严格的增长体重,我们可通过让代码运行在达到下一个之前估计两个相邻的重量
我们可形式化单调 Gray code 的概念如下:考虑超立方体的分区 $ Q_ {n} = (V_ {n}, E_ {n}) $ 为有相同重量的定点层级,例如
$ V_ {n}(i) = { \nu \in V_ {n} : \nu \quad \text{ has weight i } }, 0 \le i \le n $
这些层满足 $ | V_ {n}(i) | = \binom{n}{i} $。设 $ Q_ {n}(i) $ 为 $ Q_ {n} $ 引入 $ V_ {n}(i) \cup V_ {n}(i+1) $ 的子图,且设 $ E_ {n}(i) $ 为 $ Q_ {n}(i) $ 中的边。一个单调 Gray code 是 $ Q_ {n} $ 中一个哈密尔顿路径使得当 $ \delta_ {1} \in E_ {n}(i) $ 在 $ \delta_ {2} \in E_ {n}(j) $ 之前,则 $ i \le j $
一个对任意 n 的单调 n 位 Gray code 的伟大构建基于递归构建 $ 2 \binom{n}{j} $ 长度子路径 $ P_ {n, j} $ 其在 $ E_ {n}(j) $ 中有边。我们定义 $ P_ {1,0} = (0, 1), P_ {n,j} = \emptyset, j < 0 or j \ge n $ 且
$ P_ {n_1, j} = 1 P^{\pi_ {n}}_ {n,j-1}, 0P_ {n, j} $
这里,$ \pi_ {n} $ 是一个适合的被定义排列且 $ P^{\pi} $ 指路径 P 其坐标被 $ \pi $ 重新排列。这些路径导致两个单调 n 位 Gray code $ G^{(1)}_ {n}, G^{(2)}_ {n} $:
$ G^{(1)}_ {n} = P_ {n,0}P^{R}_ {n,1}P_ {n,2}P^{R}_ {n,3} \cdots, G^{(2)}_ {n} = P^{R}_ {n,0}P_ {n,1}P^{R}_ {n,2}P_ {n,3} \cdots $
$ \pi_ {n} $ 的选择确保这些代码为 Gray code 证明 $ \pi_ {n} = E^{-1}(\pi^{2}_ {n-1}) $。$ P_ {n, j} 的前几个显示在下表中
j = 0 | j = 1 | j = 2 | j = 3 | |
---|---|---|---|---|
n = 1 | 0, 1 | |||
n = 2 | 00, 01 | 10, 11 | ||
n = 3 | 000, 001 | 100, 110, 010, 011 | 101, 111 | |
n = 4 | 0000, 0001 | 1000, 1100, 0100, 0110, 0010, 0011 | 1010, 1011, 1001, 1101, 0101, 0111 | 1110, 1111 |
这些单调 Gray code 这样可高效实现,每个子序列元素可在 O(n) 时间复杂度下生成
单调代码有一个有趣的连接到 Lovász conjecture,其表述每个连接的定点转换图包含一个哈密尔顿路径。“中级水平”子图 $ Q_ {2n+1}(n) $ 是向量转换(即,它的自同构组是可转换的,这样每个定点有相同的“本地环境”且不能跟其他不同,因为我们可重标签坐标这样二进制数字来获得一个自同构)且在这个子图中找到一个哈密尔顿路径的问题被称为“中等层级问题“,其可提供到更一般化猜想的洞察。问对 $ n \le 15 $ 的情况题已获得肯定答复,且单调代码的后续构建确保一个至少 0.839N 长度的哈密尔顿路径,N 是中级层级子图中顶点数
Beckett-Gray code
另一种类型 Gray code,Beckett-Gray code,以爱尔兰剧作家 Samuel Beckett 命名,其在对称性上有很大的兴趣。他的剧“Quad“描写了四位演员并分割为六个时期。每个时期以一个演员进入或离开舞台结束。剧开始结束时是一个空的舞台,且 Beckette 想要演员的每个子集只出现在舞台一次。明显地当前舞台上演员的集合可呈现为 4 位二进制 Gray code。Beckette,然而,在脚本上加了另外一个限制:他希望演员进入或退出使得舞台上所在最长的演员总是存在。演员可呈现为一个先进先出队列,这样(舞台上的演员)被退出的演员总是最先入队列的。Beckette 不能找到适合他的剧的一个 Beckette Gray code,且实际上,一个完全列表所有可能的序列表明对 n = 4 没有这样的代码存在。现在知道这样的代码对 n = 2, 5, 6, 7 和 8 存在,对 n = 3 或 4 不存在。一个 8 位 Beckette-Gray code 的例子可在 Donald Knuth 的计算机编程艺术里发现。根据 Sawada 和 Wong,对 n = 6 的研究空间可被探索在 15 小时以内,且对 n = 7 的情况已发现超过 9500 种解决方案
箱中蛇代码
箱中蛇代码,或蛇,是在一个 n 维超立方体图形中包含路径的节点序列,且箱中盘代码,或盘,是在一个超立方体中包含循环的节点序列。视为 Gray code,这些序列有能检测出任意单位代码错误的属性。这种类型的代码在 1950 年末由 William H. Kautz 首次描述,之后,对一个给定超立方体维度由很多在找到最大可能代码字节数量的代码的研究
单轨 Gray code
另一种 Gray code 是由 Norman B. Spedding 开发并被 Hiltgen、Paterson 和 Brandestini 在 1996 年重定义的单轨 Gray code(STGC)。STGC 是一个长度为 n 的 P 唯一二进制编码的循环列表使得两个连续的字节只有一个位置不同,且当列表为一个 P x n 矩阵,每列是首列的一个循环位移
名称来源于他们使用的旋转编码器,轨数由联系探知,导致一个 0 或 1 的输出里的每一个结果。为减少每次在同一时刻由于不同联系不转变的噪音,一个更好的设置轨道使得联系的数据输出在 Gray code 中。为获得高尖角精确度,需要很多联系;为了达到至少 $ 1^{\circ} $ 的精确度,每个旋转需要至少 360 个不同的位置,需要一个至少 9 位的数据,且相同数量的联系
如果所有联系位于相同尖角位置,则需要 9 个轨来获得一个至少 $ 1^{ \circ } $ 的标准 BRGC 精确度。然而,如果制造商移动一个联系到一个不同尖角位置(但跟中心轴相同距离),则对应“环范型”需要被旋转相同的角度来获得相同的输出。如果最高有效位足够旋转,它精确匹配下一个环输出。因为两个环唯一确定,内环可移掉,且该环传感器移动到剩下的唯一确认的环上(但从其他传感器在那个角度在该环上)。单环上这两个传感器产生一个四边形编码器。它缩减一个 $ 1^{\circ} $ 解决方案角度编码器的轨道数为 8 个。更进一步缩减轨道数不能在 BRGC 上实现
多年来,Torsten Sillke 和其他数学家相信在单轨上不可能加密位置这样连续位置上只有一个传感器不同,除了 2-传感器,1 轨四边形编码器。这样对应用程序 8 个轨道太笨重,人们使用单轨递增编码器(四边形编码器)或 2-轨“四边形编码器+引用孔“编码器
Norman B. Spedding 在 1994 年注册了一个专利权用几个例子显示这是可能的。虽然它不可能在单轨上用 n 个传感器区分 $ 2^{n} $ 个位置,它可能区分接近该数的数目。Etzion 和 Peterson 推测当 n 是 2 的指数时,n 个传感器可区分最多 $ 2^{n} - 2n $ 个位置且对质数 n 限制是 $ 2^{n} -2 $ 个位置。作者继续产生一个长度为 9 的 504 位置单轨代码,他们相信是优化的。因为这个数比 $ 2^{8} = 256 $ 大,任意代码需要超过 8 个传感器,虽然一个 BRGC 用 9 个传感器可区分 512 个位置
对 P = 30 和 n = 5 的一个 STGC 重生成如下
角度 | 代码 | 角度 | 代码 | 角度 | 代码 | 角度 | 代码 | 角度 | 代码 |
---|---|---|---|---|---|---|---|---|---|
0 | 10000 | 72 | 01000 | 144 | 00100 | 216 | 00010 | 288 | 00001 |
12 | 10100 | 84 | 01010 | 156 | 00101 | 228 | 10010 | 300 | 01001 |
24 | 11100 | 96 | 01110 | 168 | 00111 | 240 | 10011 | 312 | 11001 |
36 | 11110 | 108 | 01111 | 180 | 10111 | 252 | 11011 | 324 | 11101 |
48 | 11010 | 120 | 01101 | 192 | 10110 | 264 | 01001 | 336 | 10101 |
60 | 11000 | 132 | 01100 | 204 | 00110 | 276 | 00011 | 348 | 10001 |
每列是首列的一个循环位移,且从任意行到下一行只有一位改变。单轨自然是有用的在这些轮子的制造上(相比 BRGC),因只有一个轨需要,这样缩减了他们的成本和大小。Gray code 自然是有用的(相比较链代码,也称为 De Bruijn 序列),因为只有一个传感器在一个时刻改变,这样两个连续状态之间只有一个增或减角度单元在转换期间设备的测量可以得到解决
因为这个 30 度的例子已添加,在更高角度解决方案的例子上有很多有趣的地方。在 2008 年,Gary Williams,基于之前的工作发现一个 9 位单轨 Gray code 给出一个 1 度的解决方案。这个 Gray code 用于设计一个实际的设备发布在网站 Thingverse 上。这个设备在 2022 年 7 月被 etzenseep(Florian Bauer)设计
一个 P = 360 且 n = 9 的 STGC 重生成如下:
角度 | 代码 | 角度 | 代码 | 角度 | 代码 | 角度 | 代码 | 角度 | 代码 | 角度 | 代码 | 角度 | 代码 | 角度 | 代码 | 角度 | 代码 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 100000001 | 40 | 000000011 | 80 | 000000110 | 120 | 000001100 | 160 | 000011000 | 200 | 000110000 | 240 | 001100000 | 280 | 011000000 | 320 | 110000000 |
1 | 110000001 | 41 | 100000011 | 81 | 000000111 | 121 | 000001110 | 161 | 000011100 | 201 | 000111000 | 241 | 001110000 | 281 | 011100000 | 321 | 111000000 |
2 | 111000001 | 42 | 110000011 | 82 | 100000111 | 122 | 000001111 | 162 | 000011110 | 202 | 000111100 | 242 | 001111000 | 282 | 011110000 | 322 | 111100000 |
3 | 111000011 | 43 | 110000111 | 83 | 100001111 | 123 | 000011111 | 163 | 000111110 | 203 | 001111100 | 243 | 011111000 | 283 | 111110000 | 323 | 111100001 |
4 | 111000111 | 44 | 110001111 | 84 | 100011111 | 124 | 000111111 | 164 | 001111110 | 204 | 011111100 | 244 | 111111000 | 284 | 111110001 | 324 | 111100011 |
5 | 111001111 | 45 | 110011111 | 85 | 100111111 | 125 | 001111111 | 165 | 011111110 | 205 | 111111100 | 245 | 111111001 | 285 | 111110011 | 325 | 111100111 |
6 | 111011111 | 46 | 110111111 | 86 | 101111111 | 126 | 011111111 | 166 | 111111110 | 206 | 111111101 | 246 | 111111011 | 286 | 111110111 | 326 | 111101111 |
7 | 111011011 | 47 | 110110111 | 87 | 101101111 | 127 | 011011111 | 167 | 110111110 | 207 | 101111101 | 247 | 011111011 | 287 | 111110110 | 327 | 111101101 |
8 | 101011011 | 48 | 010110111 | 88 | 101101110 | 128 | 011011101 | 168 | 110111010 | 208 | 101110101 | 248 | 011101011 | 288 | 111010110 | 328 | 110101101 |
9 | 101011111 | 49 | 010111111 | 89 | 101111110 | 129 | 011111101 | 169 | 111111010 | 209 | 111110101 | 249 | 111101011 | 289 | 111010111 | 329 | 110101111 |
10 | 101011101 | 50 | 010111011 | 90 | 101110110 | 130 | 011101101 | 170 | 111011010 | 210 | 110110101 | 250 | 101101011 | 290 | 011010111 | 330 | 110101110 |
11 | 101010101 | 51 | 010101011 | 91 | 101010110 | 131 | 010101101 | 171 | 101011010 | 211 | 010110101 | 251 | 101101010 | 291 | 011010101 | 331 | 110101010 |
12 | 101010111 | 52 | 010101111 | 92 | 101011110 | 132 | 010111101 | 172 | 101111010 | 212 | 011110101 | 252 | 111101010 | 292 | 111010101 | 332 | 110101011 |
13 | 101110111 | 53 | 011101111 | 93 | 111011110 | 133 | 110111101 | 173 | 101111011 | 213 | 011110111 | 253 | 111101110 | 293 | 111011101 | 333 | 110111011 |
14 | 001110111 | 54 | 011101110 | 94 | 111011100 | 134 | 110111001 | 174 | 101110011 | 214 | 011100111 | 254 | 111001110 | 294 | 110011101 | 334 | 100111011 |
15 | 001010111 | 55 | 010101110 | 95 | 101011100 | 135 | 010111001 | 175 | 101110010 | 215 | 011100101 | 255 | 111001010 | 295 | 110010101 | 335 | 100101011 |
16 | 001011111 | 56 | 010111110 | 96 | 101111100 | 136 | 011111001 | 176 | 111110010 | 216 | 111100101 | 256 | 111001011 | 296 | 110010111 | 336 | 100101111 |
17 | 001011011 | 57 | 010110110 | 97 | 101101100 | 137 | 011011001 | 177 | 110110010 | 217 | 101100101 | 257 | 011001011 | 297 | 110010110 | 337 | 100101101 |
18 | 001011001 | 58 | 010110010 | 98 | 101100100 | 138 | 011001001 | 178 | 110010010 | 218 | 100100101 | 258 | 001001011 | 298 | 010010110 | 338 | 100101100 |
19 | 001111001 | 59 | 011110010 | 99 | 111100100 | 139 | 111001001 | 179 | 110010011 | 219 | 100100111 | 259 | 001001111 | 299 | 010011110 | 339 | 100111100 |
20 | 001111101 | 60 | 011111010 | 100 | 111110100 | 140 | 111101001 | 180 | 111010011 | 220 | 110100111 | 260 | 101001111 | 300 | 010011111 | 340 | 100111110 |
21 | 000111101 | 61 | 001111010 | 101 | 011110100 | 141 | 111101000 | 181 | 111010001 | 221 | 110100011 | 261 | 101000111 | 301 | 010001111 | 341 | 100011110 |
22 | 000110101 | 62 | 001101010 | 102 | 011010100 | 142 | 110101000 | 182 | 101010001 | 222 | 010100011 | 262 | 101000110 | 302 | 010001101 | 342 | 100011010 |
23 | 000100101 | 63 | 001001010 | 103 | 010010100 | 143 | 100101000 | 183 | 001010001 | 223 | 010100010 | 263 | 101000100 | 303 | 010001001 | 343 | 100010010 |
24 | 000101101 | 64 | 001011010 | 104 | 010110100 | 144 | 101101000 | 184 | 011010001 | 224 | 110100010 | 264 | 101000101 | 304 | 010001011 | 344 | 100010110 |
25 | 000101001 | 65 | 001010010 | 105 | 010100100 | 145 | 101001000 | 185 | 010010001 | 225 | 100100010 | 265 | 001000101 | 305 | 010001010 | 345 | 100010100 |
26 | 000111001 | 66 | 001110010 | 106 | 011100100 | 146 | 111001000 | 186 | 110010001 | 226 | 100100011 | 266 | 001000111 | 306 | 010001110 | 346 | 100011100 |
27 | 000110001 | 67 | 001100010 | 107 | 011000100 | 147 | 110001000 | 187 | 100010001 | 227 | 000100011 | 267 | 001000110 | 307 | 010001100 | 347 | 100011000 |
28 | 000010001 | 68 | 000100010 | 108 | 001000100 | 148 | 010001000 | 188 | 100010000 | 228 | 000100001 | 268 | 001000010 | 308 | 010000100 | 348 | 100001000 |
29 | 000011001 | 69 | 000110010 | 109 | 001100100 | 149 | 011001000 | 189 | 110010000 | 229 | 100100001 | 269 | 001000011 | 309 | 010000110 | 349 | 100001100 |
30 | 000001001 | 70 | 000010010 | 110 | 000100100 | 150 | 001001000 | 190 | 010010000 | 230 | 100100000 | 270 | 001000001 | 310 | 010000010 | 350 | 100000100 |
31 | 100001001 | 71 | 000010011 | 111 | 000100110 | 151 | 001001100 | 191 | 010011000 | 231 | 100110000 | 271 | 001100001 | 311 | 011000010 | 351 | 110000100 |
32 | 100001101 | 72 | 000011011 | 112 | 000110110 | 152 | 001101100 | 192 | 011011000 | 232 | 110110000 | 272 | 101100001 | 312 | 011000011 | 352 | 110000110 |
33 | 100000101 | 73 | 000001011 | 113 | 000010110 | 153 | 000101100 | 193 | 001011000 | 233 | 010110000 | 273 | 101100000 | 313 | 011000001 | 353 | 110000010 |
34 | 110000101 | 74 | 100001011 | 114 | 000010111 | 154 | 000101110 | 194 | 001011100 | 234 | 010111000 | 274 | 101110000 | 314 | 011100001 | 354 | 111000010 |
35 | 010000101 | 75 | 100001010 | 115 | 000010101 | 155 | 000101010 | 195 | 001010100 | 235 | 010101000 | 275 | 101010000 | 315 | 010100001 | 355 | 101000010 |
36 | 010000111 | 76 | 100001110 | 116 | 000011101 | 156 | 000111010 | 196 | 001110100 | 236 | 011101000 | 276 | 111010000 | 316 | 110100001 | 356 | 101000011 |
37 | 010000011 | 77 | 100000110 | 117 | 000001101 | 157 | 000011010 | 197 | 000110100 | 237 | 001101000 | 277 | 011010000 | 317 | 110100000 | 357 | 101000001 |
38 | 010000001 | 78 | 100000010 | 118 | 000000101 | 158 | 000001010 | 198 | 000010100 | 238 | 000101000 | 278 | 001010000 | 318 | 010100000 | 358 | 101000000 |
39 | 000000001 | 79 | 000000010 | 119 | 000000100 | 159 | 000001000 | 199 | 000010000 | 239 | 000100000 | 279 | 001000000 | 319 | 010000000 | 359 | 100000000 |
对 9 个传感器已 40 度分割的单轨 Gray code 的 20 个轨道的开始和结束角度
开始角度 | 结束角度 | 长度 |
---|---|---|
3 | 4 | 2 |
23 | 28 | 6 |
31 | 37 | 7 |
44 | 48 | 5 |
56 | 60 | 5 |
64 | 71 | 8 |
74 | 76 | 3 |
88 | 91 | 4 |
94 | 96 | 3 |
99 | 104 | 6 |
110 | 115 | 6 |
131 | 134 | 4 |
138 | 154 | 17 |
173 | 181 | 9 |
186 | 187 | 2 |
220 | 238 | 19 |
242 | 246 | 5 |
273 | 279 | 7 |
286 | 289 | 4 |
307 | 360 | 54 |
两维 Gray code
两维 Gray code 用在通信上星座的正交幅度调制(QAM)邻接点上最小化位错误数量。在一个典型的一个位不同的编码水平和垂直邻接星座点,和 2 位不同的对焦邻接点
两维 Gray code 也用在位置确定方案上,代码应用于区域地图比如地球表面的墨卡托投影法和一个适合的两维距离函数比如曼海姆度量用来计算两个编码位置的距离,因此组合了 Hamming 距离及循环连续的墨卡托投影法的特性
过量 Gray code
如果一个特殊代码值的子段从该值中提取,例如一个 4 位 Gray code 的最后 3 位,结果代码为一个过量的 Gray code。这个代码显示如果原始值进一步增加这些提取位的统计回退属性。这个原因是 Gray 编码的值不显示溢出属性,从经典的二进制编码,当增加过最高值
例如:Gray code 的最高 3 位,7, 编码为 (0)100。添加 1 结果为 8,编码到 Gray code 为 1100。最后 3 位不溢出且如果你进一步增加原来的 4 位代码统计也回归
当与传感器工作在一个系列输出多个 Gray 编码值,应该注意是否传感器产生这些值编码在单个 Gray code 或作为独立的,否则值可能当期望溢出时出现统计回归
Gray 等距映射
双射 $ \{ 0 \leftrightarrow 00, 1 \leftrightarrow 01, 2 \leftrightarrow 11, 3 \leftrightarrow 10 \} $ 在由 Hamming 距离给定的度量上的有限域 $ \mathbb{Z}^{2}_ {2} $ 上的度量空间与 Lee 距离给定的度量上的有限环 $ \mathbb{Z}_ {4} $ 上的度量空间之间确立了一个等距映射。映射可扩展到一个 Hamming 空间 $ \mathbb{Z}^{2m}_ {2} $ 和 $ \mathbb{Z}^{m}_ {4} $ 上的一个等距映射。它的重要性依赖于确定一个在各种好的但不必须的线性代码比如在 $ \mathbb{Z}_ {4} $ 上环线性代码在 $ \mathbb{Z}^{2}_ {2} $ 上的 Gray 映射的像