二进制数到十六进制字符串的高效转换
Efficient Conversion of a Binary Number to Hexadecimal String
我正在编写一个程序，将二进制值的十六进制表示形式转换为常规字符串。因此，十六进制表示中的每个字符都将转换为字符串中的两个十六进制字符。这意味着结果将是原来的两倍； 1 个字节的十六进制表示在字符串中需要两个字节。
十六进制字符
0123456789 ;0x30 - 0x39
ABCDEF ;0x41 - 0x46
示例
0xF05C1E3A ;hex
4032568890 ;dec
会变成
0x4630354331453341 ;hex
5057600944242766657 ;dec
问题？
除了查找 table（按位运算、移位、取模等）之外，是否有任何 elegant/alternative（/有趣的）方法可以在这些状态之间进行转换？
我不是在寻找库中的函数，而是在寻找 would/should 的实现方式。有什么想法吗？
使用 pdep:
可以很容易地将半字节展开为字节
spread = _pdep_u64(raw, 0x0F0F0F0F0F0F0F0F);
现在我们必须将 0x30 添加到 0-9 范围内的字节，并将 0x41 添加到更高的字节。这可以通过 SWAR 从每个字节中减去 10 然后使用符号 select 要添加的数字来完成，例如（未测试）
H = 0x8080808080808080;
ten = 0x0A0A0A0A0A0A0A0A
cmp = ((spread | H) - (ten &~H)) ^ ((spread ^~ten) & H); // SWAR subtract
masks = ((cmp & H) >> 7) * 255;
// if x-10 is negative, take 0x30, else 0x41
add = (masks & 0x3030303030303030) | (~masks & 0x3737373737373737);
asString = spread + add;
SWAR 比较可能可以优化，因为您不需要完整的减法来实现它。
这里有一些不同的建议，包括 SIMD：http://0x80.pl/articles/convert-to-hex.html
Decimal -> Hex
只需遍历字符串并将每个字符转换为 int，然后您就可以
printf("%02x", c);
或使用sprintf保存到另一个变量
Hex -> Decimal
代码
printf("%c",16 * hexToInt('F') + hexToInt('0'));
int hexToInt(char c)
{
if(c >= 'a' && c <= 'z')
c = c - ('a' - 'A');
int sum;
sum = c / 16 - 3;
sum *= 10;
sum += c % 16;
return (sum > 9) ? sum - 1 : sum;
}
下面的文章比较了将数字转换为字符串的不同方法，十六进制数字没有涉及但是从 dec 切换到 hex 似乎不是什么大问题
@编辑
感谢您指出上述答案不相关。
没有 LUT 的常见方法是将整数拆分为半字节并将它们映射到 ASCII
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#define HI_NIBBLE(b) (((b) >> 4) & 0x0F)
#define LO_NIBBLE(b) ((b) & 0x0F)
void int64_to_char(char carr[], int64_t val){
memcpy(carr, &val, 8);
}
uint64_t inp = 0xF05C1E3A;
char tmp_st[8];
int main()
{
int64_to_char(tmp_st,inp);
printf("Sample: %x\n", inp);
printf("Result: 0x");
for (unsigned int k = 8; k; k--){
char tmp_ch = *(tmp_st+k-1);
char hi_nib = HI_NIBBLE(tmp_ch);
char lo_nib = LO_NIBBLE(tmp_ch);
if (hi_nib || lo_nib){
printf("%c%c",hi_nib+((hi_nib>9)?55:48),lo_nib+((lo_nib>9)?55:48));
}
}
printf("\n");
return 0;
}
另一种方法是使用 Allison 算法。我完全是 ASM 的菜鸟，所以我 post 我用谷歌搜索过的形式的代码。
变体 1：
ADD AL,90h
DAA
ADC AL,40h
DAA
变体 2：
CMP AL, 0Ah
SBB AL, 69h
DAS
A LUT（查找 table）C++ 变体。我没有检查生成的实际机器代码，但我相信任何现代 C++ 编译器都能抓住这个想法并编译得很好。
static const char nibble2hexChar[] { "0123456789ABCDEF" };
// 17B in total, because I'm lazy to init it per char
void byteToHex(std::ostream & out, const uint8_t value) {
out << nibble2hexChar[value>>4] << nibble2hexChar[value&0xF];
}
// this one is actually written more toward short+simple source, than performance
void dwordToHex(std::ostream & out, uint32_t value) {
int i = 8;
while (i--) {
out << nibble2hexChar[value>>28];
value <<= 4;
}
}
编辑：对于 C 代码，您只需从 std::ostream 切换到其他一些输出方式，不幸的是，您的问题缺少任何细节、您实际想要实现的目标以及为什么不使用内置的-in printf C 函数系列。
例如像这样的 C 可以写入一些 char* 输出缓冲区，转换任意数量的字节：
/**
* Writes hexadecimally formatted "n" bytes array "values" into "outputBuffer".
* Make sure there's enough space in output buffer allocated, and add zero
* terminator yourself, if you plan to use it as C-string.
*
* @Returns: pointer after the last character written.
*/
char* dataToHex(char* outputBuffer, const size_t n, const unsigned char* values) {
for (size_t i = 0; i < n; ++i) {
*outputBuffer++ = nibble2hexChar[values[i]>>4];
*outputBuffer++ = nibble2hexChar[values[i]&0xF];
}
return outputBuffer;
}
最后，我确实帮助过一个人进行代码审查，因为他在十六进制格式方面有性能瓶颈，但我在那里做了代码变体转换，没有 LUT，整个过程和其他答案 + 性能测量可能对你有指导意义，因为你可能会看到最快的解决方案不只是盲目地转换结果，而是实际上与主要操作混合，以获得更好的整体性能。所以这就是为什么我想知道您要解决什么问题，因为整个问题通常可以提供更优的解决方案，如果您只询问转换，printf("%x",..) 是安全的选择。
这是 "to hex" 转换的另一种方法：
fast C++ XOR Function
从整数到字符串的更体面的转换，从 2 到数字长度的任何基数
char *reverse(char *);
const char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char *convert(long long number, char *buff, int base)
{
char *result = (buff == NULL || base > strlen(digits) || base < 2) ? NULL : buff;
char sign = 0;
if (number < 0)
{
sign = '-';
number = -number;
}
if (result != NULL)
{
do
{
*buff++ = digits[number % base];
number /= base;
} while (number);
if(sign) *buff++ = sign;
*buff = 0;
reverse(result);
}
return result;
}
char *reverse(char *str)
{
char tmp;
int len;
if (str != NULL)
{
len = strlen(str);
for (int i = 0; i < len / 2; i++)
{
tmp = *(str + i);
*(str + i) = *(str + len - i - 1);
*(str + len - i - 1) = tmp;
}
}
return str;
}
示例 - 以 23 为基数从 -50 到 50 计数
-24 -23 -22 -21 -20 -1M -1L -1K -1J -1I -1H -1G -1F -1E -1D
-1C -1B -1A -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -M -L
-K -J -I -H -G -F -E -D -C -B -A -9 -8 -7 -6
-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
A B C D E F G H I J K L M 10 11
12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 1G
1H 1I 1J 1K 1L 1M 20 21 22 23 24
这是一个解决方案，只包含移位、and/or 和 add/subtract。也没有循环。
uint64_t x, m;
x = 0xF05C1E3A;
x = ((x & 0x00000000ffff0000LL) << 16) | (x & 0x000000000000ffffLL);
x = ((x & 0x0000ff000000ff00LL) << 8) | (x & 0x000000ff000000ffLL);
x = ((x & 0x00f000f000f000f0LL) << 4) | (x & 0x000f000f000f000fLL);
x += 0x0606060606060606LL;
m = ((x & 0x1010101010101010LL) >> 4) + 0x7f7f7f7f7f7f7f7fLL;
x += (m & 0x2a2a2a2a2a2a2a2aLL) | (~m & 0x3131313131313131LL);
以上是我经过一段时间的思考得出的简化版。以下为原答案。
uint64_t x, m;
x = 0xF05C1E3A;
x = ((x & 0x00000000ffff0000LL) << 16) | (x & 0x000000000000ffffLL);
x = ((x & 0x0000ff000000ff00LL) << 8) | (x & 0x000000ff000000ffLL);
x = ((x & 0x00f000f000f000f0LL) << 4) | (x & 0x000f000f000f000fLL);
x += 0x3636363636363636LL;
m = (x & 0x4040404040404040LL) >> 6;
x += m;
m = m ^ 0x0101010101010101LL;
x -= (m << 2) | (m << 1);
查看实际效果：http://ideone.com/nMhJ2q
基于 Mark Ransom 的稍微简单的版本：
uint64_t x = 0xF05C1E3A;
x = ((x & 0x00000000ffff0000LL) << 16) | (x & 0x000000000000ffffLL);
x = ((x & 0x0000ff000000ff00LL) << 8) | (x & 0x000000ff000000ffLL);
x = ((x & 0x00f000f000f000f0LL) << 4) | (x & 0x000f000f000f000fLL);
x = (x + 0x3030303030303030LL) +
(((x + 0x0606060606060606LL) & 0x1010101010101010LL) >> 4) * 7;
如果你想避免乘法：
uint64_t m, x = 0xF05C1E3A;
x = ((x & 0x00000000ffff0000LL) << 16) | (x & 0x000000000000ffffLL);
x = ((x & 0x0000ff000000ff00LL) << 8) | (x & 0x000000ff000000ffLL);
x = ((x & 0x00f000f000f000f0LL) << 4) | (x & 0x000f000f000f000fLL);
m = (x + 0x0606060606060606LL) & 0x1010101010101010LL;
x = (x + 0x3030303030303030LL) + (m >> 1) - (m >> 4);
我正在编写一个程序，将二进制值的十六进制表示形式转换为常规字符串。因此，十六进制表示中的每个字符都将转换为字符串中的两个十六进制字符。这意味着结果将是原来的两倍； 1 个字节的十六进制表示在字符串中需要两个字节。
十六进制字符
0123456789 ;0x30 - 0x39
ABCDEF ;0x41 - 0x46
示例
0xF05C1E3A ;hex
4032568890 ;dec
会变成
0x4630354331453341 ;hex
5057600944242766657 ;dec
问题？
除了查找 table（按位运算、移位、取模等）之外，是否有任何 elegant/alternative（/有趣的）方法可以在这些状态之间进行转换？ 我不是在寻找库中的函数，而是在寻找 would/should 的实现方式。有什么想法吗？
使用 pdep:
spread = _pdep_u64(raw, 0x0F0F0F0F0F0F0F0F);
现在我们必须将 0x30 添加到 0-9 范围内的字节，并将 0x41 添加到更高的字节。这可以通过 SWAR 从每个字节中减去 10 然后使用符号 select 要添加的数字来完成，例如（未测试）
H = 0x8080808080808080;
ten = 0x0A0A0A0A0A0A0A0A
cmp = ((spread | H) - (ten &~H)) ^ ((spread ^~ten) & H); // SWAR subtract
masks = ((cmp & H) >> 7) * 255;
// if x-10 is negative, take 0x30, else 0x41
add = (masks & 0x3030303030303030) | (~masks & 0x3737373737373737);
asString = spread + add;
SWAR 比较可能可以优化，因为您不需要完整的减法来实现它。
这里有一些不同的建议，包括 SIMD：http://0x80.pl/articles/convert-to-hex.html
Decimal -> Hex
只需遍历字符串并将每个字符转换为 int，然后您就可以
printf("%02x", c);
或使用sprintf保存到另一个变量
Hex -> Decimal
代码
printf("%c",16 * hexToInt('F') + hexToInt('0'));
int hexToInt(char c)
{
if(c >= 'a' && c <= 'z')
c = c - ('a' - 'A');
int sum;
sum = c / 16 - 3;
sum *= 10;
sum += c % 16;
return (sum > 9) ? sum - 1 : sum;
}
下面的文章比较了将数字转换为字符串的不同方法，十六进制数字没有涉及但是从 dec 切换到 hex 似乎不是什么大问题
@编辑 感谢您指出上述答案不相关。 没有 LUT 的常见方法是将整数拆分为半字节并将它们映射到 ASCII
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#define HI_NIBBLE(b) (((b) >> 4) & 0x0F)
#define LO_NIBBLE(b) ((b) & 0x0F)
void int64_to_char(char carr[], int64_t val){
memcpy(carr, &val, 8);
}
uint64_t inp = 0xF05C1E3A;
char tmp_st[8];
int main()
{
int64_to_char(tmp_st,inp);
printf("Sample: %x\n", inp);
printf("Result: 0x");
for (unsigned int k = 8; k; k--){
char tmp_ch = *(tmp_st+k-1);
char hi_nib = HI_NIBBLE(tmp_ch);
char lo_nib = LO_NIBBLE(tmp_ch);
if (hi_nib || lo_nib){
printf("%c%c",hi_nib+((hi_nib>9)?55:48),lo_nib+((lo_nib>9)?55:48));
}
}
printf("\n");
return 0;
}
另一种方法是使用 Allison 算法。我完全是 ASM 的菜鸟，所以我 post 我用谷歌搜索过的形式的代码。
变体 1：
ADD AL,90h
DAA
ADC AL,40h
DAA
变体 2：
CMP AL, 0Ah
SBB AL, 69h
DAS
A LUT（查找 table）C++ 变体。我没有检查生成的实际机器代码，但我相信任何现代 C++ 编译器都能抓住这个想法并编译得很好。
static const char nibble2hexChar[] { "0123456789ABCDEF" };
// 17B in total, because I'm lazy to init it per char
void byteToHex(std::ostream & out, const uint8_t value) {
out << nibble2hexChar[value>>4] << nibble2hexChar[value&0xF];
}
// this one is actually written more toward short+simple source, than performance
void dwordToHex(std::ostream & out, uint32_t value) {
int i = 8;
while (i--) {
out << nibble2hexChar[value>>28];
value <<= 4;
}
}
编辑：对于 C 代码，您只需从 std::ostream 切换到其他一些输出方式，不幸的是，您的问题缺少任何细节、您实际想要实现的目标以及为什么不使用内置的-in printf C 函数系列。
例如像这样的 C 可以写入一些 char* 输出缓冲区，转换任意数量的字节：
/**
* Writes hexadecimally formatted "n" bytes array "values" into "outputBuffer".
* Make sure there's enough space in output buffer allocated, and add zero
* terminator yourself, if you plan to use it as C-string.
*
* @Returns: pointer after the last character written.
*/
char* dataToHex(char* outputBuffer, const size_t n, const unsigned char* values) {
for (size_t i = 0; i < n; ++i) {
*outputBuffer++ = nibble2hexChar[values[i]>>4];
*outputBuffer++ = nibble2hexChar[values[i]&0xF];
}
return outputBuffer;
}
最后，我确实帮助过一个人进行代码审查，因为他在十六进制格式方面有性能瓶颈，但我在那里做了代码变体转换，没有 LUT，整个过程和其他答案 + 性能测量可能对你有指导意义，因为你可能会看到最快的解决方案不只是盲目地转换结果，而是实际上与主要操作混合，以获得更好的整体性能。所以这就是为什么我想知道您要解决什么问题，因为整个问题通常可以提供更优的解决方案，如果您只询问转换，printf("%x",..) 是安全的选择。
这是 "to hex" 转换的另一种方法： fast C++ XOR Function
从整数到字符串的更体面的转换，从 2 到数字长度的任何基数
char *reverse(char *);
const char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char *convert(long long number, char *buff, int base)
{
char *result = (buff == NULL || base > strlen(digits) || base < 2) ? NULL : buff;
char sign = 0;
if (number < 0)
{
sign = '-';
number = -number;
}
if (result != NULL)
{
do
{
*buff++ = digits[number % base];
number /= base;
} while (number);
if(sign) *buff++ = sign;
*buff = 0;
reverse(result);
}
return result;
}
char *reverse(char *str)
{
char tmp;
int len;
if (str != NULL)
{
len = strlen(str);
for (int i = 0; i < len / 2; i++)
{
tmp = *(str + i);
*(str + i) = *(str + len - i - 1);
*(str + len - i - 1) = tmp;
}
}
return str;
}
示例 - 以 23 为基数从 -50 到 50 计数
-24 -23 -22 -21 -20 -1M -1L -1K -1J -1I -1H -1G -1F -1E -1D -1C -1B -1A -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -M -L -K -J -I -H -G -F -E -D -C -B -A -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 1G 1H 1I 1J 1K 1L 1M 20 21 22 23 24
这是一个解决方案，只包含移位、and/or 和 add/subtract。也没有循环。
uint64_t x, m;
x = 0xF05C1E3A;
x = ((x & 0x00000000ffff0000LL) << 16) | (x & 0x000000000000ffffLL);
x = ((x & 0x0000ff000000ff00LL) << 8) | (x & 0x000000ff000000ffLL);
x = ((x & 0x00f000f000f000f0LL) << 4) | (x & 0x000f000f000f000fLL);
x += 0x0606060606060606LL;
m = ((x & 0x1010101010101010LL) >> 4) + 0x7f7f7f7f7f7f7f7fLL;
x += (m & 0x2a2a2a2a2a2a2a2aLL) | (~m & 0x3131313131313131LL);
以上是我经过一段时间的思考得出的简化版。以下为原答案。
uint64_t x, m;
x = 0xF05C1E3A;
x = ((x & 0x00000000ffff0000LL) << 16) | (x & 0x000000000000ffffLL);
x = ((x & 0x0000ff000000ff00LL) << 8) | (x & 0x000000ff000000ffLL);
x = ((x & 0x00f000f000f000f0LL) << 4) | (x & 0x000f000f000f000fLL);
x += 0x3636363636363636LL;
m = (x & 0x4040404040404040LL) >> 6;
x += m;
m = m ^ 0x0101010101010101LL;
x -= (m << 2) | (m << 1);
查看实际效果：http://ideone.com/nMhJ2q
基于 Mark Ransom 的稍微简单的版本：
uint64_t x = 0xF05C1E3A;
x = ((x & 0x00000000ffff0000LL) << 16) | (x & 0x000000000000ffffLL);
x = ((x & 0x0000ff000000ff00LL) << 8) | (x & 0x000000ff000000ffLL);
x = ((x & 0x00f000f000f000f0LL) << 4) | (x & 0x000f000f000f000fLL);
x = (x + 0x3030303030303030LL) +
(((x + 0x0606060606060606LL) & 0x1010101010101010LL) >> 4) * 7;
如果你想避免乘法：
uint64_t m, x = 0xF05C1E3A;
x = ((x & 0x00000000ffff0000LL) << 16) | (x & 0x000000000000ffffLL);
x = ((x & 0x0000ff000000ff00LL) << 8) | (x & 0x000000ff000000ffLL);
x = ((x & 0x00f000f000f000f0LL) << 4) | (x & 0x000f000f000f000fLL);
m = (x + 0x0606060606060606LL) & 0x1010101010101010LL;
x = (x + 0x3030303030303030LL) + (m >> 1) - (m >> 4);