如何在不使用任何内置方法或函数的情况下,在恒定时间(O(1))中获取字母(1-26)中字符的数值/位置？

Question

如何在不使用任何内置方法或功能且不关心角色的情况下,在恒定时间(O(1))中获得字母(1-26)中字符的数值/位置？

Answer 1

如果你的编译器支持二进制文字,你可以使用

int value = 0b00011111 & character;

如果没有,则可以使用31而不是0b00011111,因为它们是等效的.

int value = 31 & character;

或者如果你想使用十六进制

int value = 0x1F & character;

或八进制

int value = 037 & character;

您可以使用任何方式表示值31.

这是有效的,因为在ASCII中,大写字母值以011为前缀,大写字母为010,然后是二进制等效值1-26.通过使用00011111的位掩码和AND操作数,我们将3个最高有效位转换为零.这给我们留下00001到11010,1到26.

Answer 2

加上Charles Staal的非常好的(自我)答案.

假设ascii编码以下将起作用.更新了Yves Daoust的评论

int Get1BasedIndex(char ch) {
  return ( ch | ('a' ^ 'A') ) - 'a' + 1;
}

这将使字符大写并更改索引.

但是更可读的解决方案(O(1))是:

int Get1BasedIndex(char ch) {
  return ('a' <= ch && ch <= 'z') ? ch - 'a' + 1 : ch - 'A' + 1;
}

另一个解决方案是恒定时间但需要一些额外的内存是:

static int cha[256];

static void init() {
  int code = -1;
  fill_n (&cha[0], &cha[256], code);
  code = 1;
  for(char s = 'a', l = 'A'; s <= 'z'; ++s, ++l) {
    cha[s] = cha[l] = code++;
  }
}

int Get1BasedIndex(char ch) {
  return cha[ch];
}