16バイトの値を10進数として表示するコードの意味

以下は、16バイトの値を10進数として表示するプログラムらしいのですが、何をしているかがわかりません…。なぜk1に6をかけるのでしょうか？0x1999999999999999とはなんでしょうか？

このコードの意味がわかる方、ご回答をお願い致します。

c
1#include <stdio.h>
2#include <stdint.h>
3
4int main(void){
5    uint64_t hi = 0xFFFFFFFFFFFFFFFF;
6    uint64_t lo = 0xFFFFFFFFFFFFFFFF;
7    char buf[40] = {};
8    char *s = buf + 39;
9    do {
10        int k1 = hi % 10;
11        uint64_t k2 = k1 * 6 + lo;
12        if (lo > -99) {
13            k2 -= 90;
14            *--s = '0' + k2 % 10;
15            lo = k2 / 10 + 0x1999999999999999 * k1 + 9;
16        } else {
17            *--s = '0' + k2 % 10;
18            lo = k2 / 10 + 0x1999999999999999 * k1;
19        }
20        hi /= 10;
21    } while (lo || hi);
22    printf("%s\n",s);       //=> 340282366920938463463374607431768211455
23    return 0;
24}

Bakudankun

2018/01/12 14:35

0x1999999999999999 は 0xFFFFFFFFFFFFFFFF ÷ 10 (つまり0xA) の商ですね。if文の条件式が誤読を呼びそうな書き方をされていますが原文通りですか？

toshiyan

2018/01/13 00:48

申し訳ございません。原文を整形する過程で誤った箇所にスペースを入れてしまいました…。修正しました。

行動規範の内容に同意します

回答1件

ベストアンサー

全部はみてないですが、

なぜk1に6をかけるのでしょうか

ここだけヒントになりそうなことを思いついたのでコメントしてみます。

HIとLOの意味はおわかりと思います。

実際の値は

HI * 2^64 + LO

として表現しているのだろうと思います。さて、十進数にする際には普通10で割りながら余りを求めそれが次の桁になるというのはよろしいですね？要するに10で割ったあまりを出さなければなりません。

(HI*2^64 + LO) % 10
= ((HI * 2^64) % 10 + LO % 10) % 10
= ((HI % 10) * (2^64)%10 + LO % 10) % 10
ですね？
2^64%10は一々計算させるまでもなく6なのでご質問のコードでは6と書いてあるのでしょう。

pythonなどでは長精度整数が手軽に計算できるのですが殆どその恩恵にあずかる機会はないように思います。そこで、この問題を拝見してせっかくなので(1<<64)%10とやってみました。予想どおり6となりました。

0x1999999999999999とはなんでしょうか？

本件は多倍長整数の演算をいかに効率よくやるかに工夫を凝らしてあるというところがポイントだと思うので、上にコメントした「なぜ6か」という話と同様「こういう計算をしたいはず」という予想を立てつつ自分で実装するつもりで見ていくと意図が見えてきやすいと思います。こういうものは「愚直な方法」ではやってません。それなりの工夫が凝らされているはずです。

自分は0x1999999999999999が何かについて答えを持ってませんが、色々考えてわかったときはきっと感動すると思いますので、そこは質問者さん、あるいは他の方にお譲りします。

全然関係ないですが、32bitの整数の1のビットの数を求めるのに

uint32_t i = ...;
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
return i & 0x3f;

こんな方法があるのをご存知でしょうか。これはJavaの標準ライブラリーの中に出てくる実装ですけど、こうしたものも「愚直な実装ではない」ため「それなりに考えないとなんでそれでうまくいくのか意味不明」に見えると思います。しかし落ち着いてよく考えればわかります。

こういうのは論理を考える訓練にもなるので色々時間をかけて考えてみてもいいのではないでしょうか。

投稿2018/01/12 12:46

KSwordOfHaste

総合スコア18394

KSwordOfHaste

2018/01/12 13:31

pythonで計算しましたのくだりですが・・・2^4が16で6x6=36なので2^(4*N)の下一桁が6であるのは自明ですよね、抜けたことを書いてしまいました。失礼しました orz

toshiyan

2018/01/13 01:11

回答ありがとうございます！回答者様の回答を元に考えたところ、このプログラムで行われていることがだいたいわかりました。このコードには色々と不可解なところがあります。変数loはuint64_t型であり、0未満になることはありえないのに「lo > -99」という条件式があります。数学の世界では、これは必ず真になりますが、コンピュータの世界では違うのですね。-99の64ビット表現は「FFFFFFFFFFFFFF9D」であり、これを見て納得がいきました。-99は、左辺のuint64_t型と解釈されるのですね。「lo > -99」は、k2がオーバーフローしてしまうかもしれない条件を表し、k2 -= 90;はオーバーフローしておかしくなった値を元に戻しているみたいです。-90することによってk2の2桁目が9マイナスされたため、それを元に戻すために、その後で変数loに9を足しているようです。しかし、0x1999999999999999の謎は未だにわからないままです…。ある程度の予想はつきますが、それがなぜ0x19..9なのかが、よくわかりません。回答者様のおっしゃるように、「こういう計算をしたいはず」という予想を立てながら考えました。すると、どうやらこれは「loの先頭に、hiの一桁目だった値を付けている」みたいなのです。「1234567890」という数字があり、これが「hi = 12345」「lo = 67890」と分かれていたと考えると、hiとloをそれぞれ10で割ると「hi = 1234」「lo = 6789」となり、5がなくなってしまいます。このなくなってしまった5を付け加えるために、0x19..9 * 5 をloに足しているようなのです。そこまではわかりました。もうすぐで答えは出そうです。ありがとうございました！

KSwordOfHaste

2018/01/13 02:31

> コンピュータの世界では違うのですね。おっしゃるとおり、普通の常識とはまた違った独特のルールがあるので注意が必要ですね。言語によっても違いますし。例えばCでunsignedとsingedの演算(比較等)をした場合どう解釈されるかの仕様を把握していないと正解にたどり着けないまま「なんで？！」となると思います。こうした点に混乱した経験は誰でも持っているのではないでしょうか？自分にはプログラミングのパズル的な側面のようにも感じます。

toshiyan

2018/01/13 02:55

コードの意味を完全に理解できましたので解決済みとします。いつか自分の力で、上記のようなコードを書けるようになりたいです。回答ありがとうございました！

KSwordOfHaste

2018/01/13 03:27 編集

多分こういうものに対する挑戦する心構えさえあれば大抵のものは怖くないと思います。こういうものに触れるにつけ、そこに流れる考え方やトリックについて知識が増えていき、自分で論理を考える場合のみならず、既にある複雑なアルゴリズムを把握するためにもきっと役立つだろうと思います。自分はほんの少ししかヒントらしきものを言ってませんので、質問者さんがこの問題を解決されたのはご自身の力だと自信をもってよいと思いました。（ちなみに自分は頭が固い方なので多分同じ時間で解ける自信ないですｗ；）

行動規範の内容に同意します