十六进制和算法
Hex sum algorithm
能否请您告知是否有任何有效的方法来计算十六进制的两个数字之和而不将它们转换为 base10?我知道如何手动计算总和(实际上与 base10 相同),但也许有更有效的方法?我将在 ABAP 中实现该算法,该算法能够计算十六进制最大 4 字节长度的总和。
免责声明:我不了解 ABAP,所以在某些方面我可能完全不了解。
求和本质上是在两位数相加的复杂度和位数之间进行权衡。在硬件层面,数字是用二进制表示的,所以每个 digit addition 都相当容易,但是有很多。当您进行任意大小(或大整数)运算时,您通常会避免在软件中实现这些位级操作,而是将更多的位组合成一个逻辑数字。如果将 4 位组合在一起,最终会得到十六进制的长加法。
但是您可以通过将多个十六进制数字组合成一个数字来组成更大的数字。如果您的机器允许每个数字不超过 4 个字节,那么我将取该数字的一半,即每个数字 2 个字节或 16 位。因此,您将四个十六进制数字组成一组,将它们组合成一个数字(这将以 10 为基数表示,但由于您只是用它计算,而不是打印它,它在内部以 2 为基数,至少在我知道的语言中是这样)并执行除了那些。两个 16 位数字相加的结果将有 17 位。其中,最低有效的 16 位构成结果的一位数,而最高有效位是下一位的进位。将结果数字转回十六进制字符串时,请确保在再次连接之前每个数字都用零填充为 4 个十六进制数字。
一些架构有一个进位标志,所以它们可以将整个寄存器宽度(在你的例子中是 4 个字节)作为一个数字,并且仍然知道是否要在下一个位置添加一个进位。但是从高级语言访问它往往很乏味,这就是为什么我建议你使用一半的寄存器宽度。
请注意,与将每个数字单独相加相比,数字分组、填充和连接会使代码复杂得多。您必须评估性能提升是否真的需要增加复杂性。
只需使用 X 类型的变量,如下例所示:
REPORT Y_HEX_SUM.
PARAMETERS: p_h1(4) type c DEFAULT 'BAFF',
p_h2(4) type c DEFAULT '1234'.
data: g_h1(2) type x, " This works in Unicode systems, otherwise make length 4.
g_h2(2) type x,
g_sum(2) type x.
START-OF-SELECTION.
g_h1 = p_h1.
g_h2 = p_h2.
g_sum = g_h1 + g_h2.
write: / g_h1, '+', g_h2, '=', g_sum.
在不更改输入参数的情况下,这将输出:
BAFF + 1234 = CD33
将两个用数字 0123456789ABCDEF 表示的以 16 为底的数字相加与对通常的以 10 为底的表示相加没有什么不同,当然除了求和 table 不同之外。像往常一样,您需要随身携带。求和table是一个对称矩阵,这是它的上层表示(这里没有ABAP,抱歉!希望你能读懂Kotlin)
private const val CARRY = '1'
private val ST = arrayOf( // summation table base 16
/* 0 1 2 3 4 5 6 7 8 9 A B C D E F */
/* 0 */ arrayOf(Pair(null,'0'),Pair(null,'1'),Pair(null,'2'),Pair(null,'3'),Pair(null,'4'),Pair(null,'5'),Pair(null,'6'),Pair(null,'7'),Pair(null,'8'), Pair(null,'9'),Pair(null,'A'), Pair(null,'B'), Pair(null,'C'), Pair(null,'D'), Pair(null,'E'), Pair(null,'F')),
/* 1 */ arrayOf( Pair(null,'2'),Pair(null,'3'),Pair(null,'4'),Pair(null,'5'),Pair(null,'6'),Pair(null,'7'),Pair(null,'8'),Pair(null, '9'), Pair(null,'A'),Pair(null,'B'), Pair(null,'C'), Pair(null,'D'), Pair(null,'E'), Pair(null,'F'), Pair(CARRY,'0')),
/* 2 */ arrayOf( Pair(null,'4'),Pair(null,'5'),Pair(null,'6'),Pair(null,'7'),Pair(null,'8'),Pair(null,'9'),Pair(null, 'A'), Pair(null,'B'),Pair(null,'C'), Pair(null,'D'), Pair(null,'E'), Pair(null,'F'), Pair(CARRY,'0'),Pair(CARRY,'1')),
/* 3 */ arrayOf( Pair(null,'6'),Pair(null,'7'),Pair(null,'8'),Pair(null,'9'),Pair(null,'A'),Pair(null, 'B'), Pair(null,'C'),Pair(null,'D'), Pair(null,'E'), Pair(null,'F'), Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2')),
/* 4 */ arrayOf( Pair(null,'8'),Pair(null,'9'),Pair(null,'A'),Pair(null,'B'),Pair(null, 'C'), Pair(null,'D'),Pair(null,'E'), Pair(null,'F'), Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3')),
/* 5 */ arrayOf( Pair(null,'A'),Pair(null,'B'),Pair(null,'C'),Pair(null, 'D'), Pair(null,'E'),Pair(null,'F'), Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4')),
/* 6 */ arrayOf( Pair(null,'C'),Pair(null,'D'),Pair(null, 'E'), Pair(null,'F'),Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4'),Pair(CARRY,'5')),
/* 7 */ arrayOf( Pair(null,'E'),Pair(null, 'F'),Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4'),Pair(CARRY,'5'),Pair(CARRY,'6')),
/* 8 */ arrayOf( Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4'),Pair(CARRY,'5'),Pair(CARRY,'6'),Pair(CARRY,'7')),
/* 9 */ arrayOf( Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4'),Pair(CARRY,'5'),Pair(CARRY,'6'),Pair(CARRY,'7'),Pair(CARRY,'8')),
/* A */ arrayOf( Pair(CARRY,'4'),Pair(CARRY,'5'),Pair(CARRY,'6'),Pair(CARRY,'7'),Pair(CARRY,'8'),Pair(CARRY,'9')),
/* B */ arrayOf( Pair(CARRY,'6'),Pair(CARRY,'7'),Pair(CARRY,'8'),Pair(CARRY,'9'),Pair(CARRY,'A')),
/* C */ arrayOf( Pair(CARRY,'8'),Pair(CARRY,'9'),Pair(CARRY,'A'),Pair(CARRY,'B')),
/* D */ arrayOf( Pair(CARRY,'A'),Pair(CARRY,'B'),Pair(CARRY,'C')),
/* E */ arrayOf( Pair(CARRY,'C'),Pair(CARRY,'D')),
/* F */ arrayOf( Pair(CARRY,'E')),
)
总和是可交换的;例如,'A' 和 '7' 的总和位于上面相同 row/col 的交集,在这种情况下 Pair(CARRY,'1')
即 '1' 并且有一个进位。这是 Kotlin 中可能实现的核心:
fun hexCharSum(a: Char, b: Char): Pair<Char?, Char> {
check(a in hexSymbolSet && b in hexSymbolSet) { "$a, $b should be in $hexSymbolSet" }
val i = a.hex2dec()
val j = b.hex2dec()
return when {
i < j -> ST[i][j-i]
j < i -> ST[j][i-j]
else -> ST[i][0]
}
}
要对两个多位数字求和,该算法在直观上是直接的,并且是 O(n) 的位数:只需将每个数字从最低有效位到最高有效位相加,记住进位。像往常一样,实施充满了额外的细节复杂性。
这是 Kotlin 中可能实现的核心:
fun hexStringSum(a: String, b: String): String {
check(regex09AF.matches(a) && regex09AF.matches(b)) { "$a, $b must be unsigned hexadecimal numbers" }
val al = a.length
val bl = b.length
fun zipAssemble(zipLength: Int, ar: String, br: String, sb: StringBuilder): Pair<Char?, StringBuilder> {
var lastCarry: Char? = null
for (ix in (0 until zipLength)) {
val aux = hexCharSum(ar[ix], br[ix])
val res = if (0 == ix) aux else lastCarry?.let { lastCy ->
aux.first?.let {
/* keep track of aux's known carry */ Pair(aux.first, hexCharSum(aux.second, lastCy).second)
} ?: hexCharSum(aux.second, lastCy)
} ?: aux
lastCarry = res.first
sb.append(res.second)
}
return Pair(lastCarry, sb)
}
fun complete(startIx: Int, endIx: Int, srcr: String, sb: StringBuilder, lastCarry: Char?): StringBuilder {
var thisCarry: Char? = lastCarry
for (ix in (startIx until endIx)) {
val res = thisCarry?.let {
hexCharSum(srcr[ix], it)
} ?: Pair(null, srcr[ix])
thisCarry = res.first
sb.append(res.second)
}
return thisCarry?.let { sb.append(CARRY) } ?: sb
}
return when {
0 == al -> b
0 == bl -> a
else -> {
val ar = a.reversed()
val br = b.reversed()
val sb = StringBuilder()
when {
al < bl -> {
val (lastCarry, sbAlias) = zipAssemble(al, ar, br, sb)
complete(al, bl, br.uppercase(), sbAlias, lastCarry).reverse().toString()
}
bl < al -> {
val (lastCarry, sbAlias) = zipAssemble(bl, ar, br, sb)
complete(bl, al, ar.uppercase(), sbAlias, lastCarry).reverse().toString()
}
else -> {
val (lastCarry, sbAlias) = zipAssemble(al, ar, br, sb)
lastCarry?.let { sbAlias.append(CARRY) }
sbAlias.reverse().toString()
}
}
}
}
}
能否请您告知是否有任何有效的方法来计算十六进制的两个数字之和而不将它们转换为 base10?我知道如何手动计算总和(实际上与 base10 相同),但也许有更有效的方法?我将在 ABAP 中实现该算法,该算法能够计算十六进制最大 4 字节长度的总和。
免责声明:我不了解 ABAP,所以在某些方面我可能完全不了解。
求和本质上是在两位数相加的复杂度和位数之间进行权衡。在硬件层面,数字是用二进制表示的,所以每个 digit addition 都相当容易,但是有很多。当您进行任意大小(或大整数)运算时,您通常会避免在软件中实现这些位级操作,而是将更多的位组合成一个逻辑数字。如果将 4 位组合在一起,最终会得到十六进制的长加法。
但是您可以通过将多个十六进制数字组合成一个数字来组成更大的数字。如果您的机器允许每个数字不超过 4 个字节,那么我将取该数字的一半,即每个数字 2 个字节或 16 位。因此,您将四个十六进制数字组成一组,将它们组合成一个数字(这将以 10 为基数表示,但由于您只是用它计算,而不是打印它,它在内部以 2 为基数,至少在我知道的语言中是这样)并执行除了那些。两个 16 位数字相加的结果将有 17 位。其中,最低有效的 16 位构成结果的一位数,而最高有效位是下一位的进位。将结果数字转回十六进制字符串时,请确保在再次连接之前每个数字都用零填充为 4 个十六进制数字。
一些架构有一个进位标志,所以它们可以将整个寄存器宽度(在你的例子中是 4 个字节)作为一个数字,并且仍然知道是否要在下一个位置添加一个进位。但是从高级语言访问它往往很乏味,这就是为什么我建议你使用一半的寄存器宽度。
请注意,与将每个数字单独相加相比,数字分组、填充和连接会使代码复杂得多。您必须评估性能提升是否真的需要增加复杂性。
只需使用 X 类型的变量,如下例所示:
REPORT Y_HEX_SUM.
PARAMETERS: p_h1(4) type c DEFAULT 'BAFF',
p_h2(4) type c DEFAULT '1234'.
data: g_h1(2) type x, " This works in Unicode systems, otherwise make length 4.
g_h2(2) type x,
g_sum(2) type x.
START-OF-SELECTION.
g_h1 = p_h1.
g_h2 = p_h2.
g_sum = g_h1 + g_h2.
write: / g_h1, '+', g_h2, '=', g_sum.
在不更改输入参数的情况下,这将输出:
BAFF + 1234 = CD33
将两个用数字 0123456789ABCDEF 表示的以 16 为底的数字相加与对通常的以 10 为底的表示相加没有什么不同,当然除了求和 table 不同之外。像往常一样,您需要随身携带。求和table是一个对称矩阵,这是它的上层表示(这里没有ABAP,抱歉!希望你能读懂Kotlin)
private const val CARRY = '1'
private val ST = arrayOf( // summation table base 16
/* 0 1 2 3 4 5 6 7 8 9 A B C D E F */
/* 0 */ arrayOf(Pair(null,'0'),Pair(null,'1'),Pair(null,'2'),Pair(null,'3'),Pair(null,'4'),Pair(null,'5'),Pair(null,'6'),Pair(null,'7'),Pair(null,'8'), Pair(null,'9'),Pair(null,'A'), Pair(null,'B'), Pair(null,'C'), Pair(null,'D'), Pair(null,'E'), Pair(null,'F')),
/* 1 */ arrayOf( Pair(null,'2'),Pair(null,'3'),Pair(null,'4'),Pair(null,'5'),Pair(null,'6'),Pair(null,'7'),Pair(null,'8'),Pair(null, '9'), Pair(null,'A'),Pair(null,'B'), Pair(null,'C'), Pair(null,'D'), Pair(null,'E'), Pair(null,'F'), Pair(CARRY,'0')),
/* 2 */ arrayOf( Pair(null,'4'),Pair(null,'5'),Pair(null,'6'),Pair(null,'7'),Pair(null,'8'),Pair(null,'9'),Pair(null, 'A'), Pair(null,'B'),Pair(null,'C'), Pair(null,'D'), Pair(null,'E'), Pair(null,'F'), Pair(CARRY,'0'),Pair(CARRY,'1')),
/* 3 */ arrayOf( Pair(null,'6'),Pair(null,'7'),Pair(null,'8'),Pair(null,'9'),Pair(null,'A'),Pair(null, 'B'), Pair(null,'C'),Pair(null,'D'), Pair(null,'E'), Pair(null,'F'), Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2')),
/* 4 */ arrayOf( Pair(null,'8'),Pair(null,'9'),Pair(null,'A'),Pair(null,'B'),Pair(null, 'C'), Pair(null,'D'),Pair(null,'E'), Pair(null,'F'), Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3')),
/* 5 */ arrayOf( Pair(null,'A'),Pair(null,'B'),Pair(null,'C'),Pair(null, 'D'), Pair(null,'E'),Pair(null,'F'), Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4')),
/* 6 */ arrayOf( Pair(null,'C'),Pair(null,'D'),Pair(null, 'E'), Pair(null,'F'),Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4'),Pair(CARRY,'5')),
/* 7 */ arrayOf( Pair(null,'E'),Pair(null, 'F'),Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4'),Pair(CARRY,'5'),Pair(CARRY,'6')),
/* 8 */ arrayOf( Pair(CARRY,'0'),Pair(CARRY,'1'),Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4'),Pair(CARRY,'5'),Pair(CARRY,'6'),Pair(CARRY,'7')),
/* 9 */ arrayOf( Pair(CARRY,'2'),Pair(CARRY,'3'),Pair(CARRY,'4'),Pair(CARRY,'5'),Pair(CARRY,'6'),Pair(CARRY,'7'),Pair(CARRY,'8')),
/* A */ arrayOf( Pair(CARRY,'4'),Pair(CARRY,'5'),Pair(CARRY,'6'),Pair(CARRY,'7'),Pair(CARRY,'8'),Pair(CARRY,'9')),
/* B */ arrayOf( Pair(CARRY,'6'),Pair(CARRY,'7'),Pair(CARRY,'8'),Pair(CARRY,'9'),Pair(CARRY,'A')),
/* C */ arrayOf( Pair(CARRY,'8'),Pair(CARRY,'9'),Pair(CARRY,'A'),Pair(CARRY,'B')),
/* D */ arrayOf( Pair(CARRY,'A'),Pair(CARRY,'B'),Pair(CARRY,'C')),
/* E */ arrayOf( Pair(CARRY,'C'),Pair(CARRY,'D')),
/* F */ arrayOf( Pair(CARRY,'E')),
)
总和是可交换的;例如,'A' 和 '7' 的总和位于上面相同 row/col 的交集,在这种情况下 Pair(CARRY,'1')
即 '1' 并且有一个进位。这是 Kotlin 中可能实现的核心:
fun hexCharSum(a: Char, b: Char): Pair<Char?, Char> {
check(a in hexSymbolSet && b in hexSymbolSet) { "$a, $b should be in $hexSymbolSet" }
val i = a.hex2dec()
val j = b.hex2dec()
return when {
i < j -> ST[i][j-i]
j < i -> ST[j][i-j]
else -> ST[i][0]
}
}
要对两个多位数字求和,该算法在直观上是直接的,并且是 O(n) 的位数:只需将每个数字从最低有效位到最高有效位相加,记住进位。像往常一样,实施充满了额外的细节复杂性。 这是 Kotlin 中可能实现的核心:
fun hexStringSum(a: String, b: String): String {
check(regex09AF.matches(a) && regex09AF.matches(b)) { "$a, $b must be unsigned hexadecimal numbers" }
val al = a.length
val bl = b.length
fun zipAssemble(zipLength: Int, ar: String, br: String, sb: StringBuilder): Pair<Char?, StringBuilder> {
var lastCarry: Char? = null
for (ix in (0 until zipLength)) {
val aux = hexCharSum(ar[ix], br[ix])
val res = if (0 == ix) aux else lastCarry?.let { lastCy ->
aux.first?.let {
/* keep track of aux's known carry */ Pair(aux.first, hexCharSum(aux.second, lastCy).second)
} ?: hexCharSum(aux.second, lastCy)
} ?: aux
lastCarry = res.first
sb.append(res.second)
}
return Pair(lastCarry, sb)
}
fun complete(startIx: Int, endIx: Int, srcr: String, sb: StringBuilder, lastCarry: Char?): StringBuilder {
var thisCarry: Char? = lastCarry
for (ix in (startIx until endIx)) {
val res = thisCarry?.let {
hexCharSum(srcr[ix], it)
} ?: Pair(null, srcr[ix])
thisCarry = res.first
sb.append(res.second)
}
return thisCarry?.let { sb.append(CARRY) } ?: sb
}
return when {
0 == al -> b
0 == bl -> a
else -> {
val ar = a.reversed()
val br = b.reversed()
val sb = StringBuilder()
when {
al < bl -> {
val (lastCarry, sbAlias) = zipAssemble(al, ar, br, sb)
complete(al, bl, br.uppercase(), sbAlias, lastCarry).reverse().toString()
}
bl < al -> {
val (lastCarry, sbAlias) = zipAssemble(bl, ar, br, sb)
complete(bl, al, ar.uppercase(), sbAlias, lastCarry).reverse().toString()
}
else -> {
val (lastCarry, sbAlias) = zipAssemble(al, ar, br, sb)
lastCarry?.let { sbAlias.append(CARRY) }
sbAlias.reverse().toString()
}
}
}
}
}