質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

91.05%

  • C

    2958questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 172

toshiyan

score 33

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

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

#include <stdio.h>
#include <stdint.h>

int main(void){
    uint64_t hi = 0xFFFFFFFFFFFFFFFF;
    uint64_t lo = 0xFFFFFFFFFFFFFFFF;
    char buf[40] = {};
    char *s = buf + 39;
    do {
        int k1 = hi % 10;
        uint64_t k2 = k1 * 6 + lo;
        if (lo > -99) {
            k2 -= 90;
            *--s = '0' + k2 % 10;
            lo = k2 / 10 + 0x1999999999999999 * k1 + 9;
        } else {
            *--s = '0' + k2 % 10;
            lo = k2 / 10 + 0x1999999999999999 * k1;
        }
        hi /= 10;
    } while (lo || hi);
    printf("%s\n",s);       //=> 340282366920938463463374607431768211455
    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • Bakudankun

    2018/01/12 23:35

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

    キャンセル

  • toshiyan

    2018/01/13 09:48

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

    キャンセル

回答 1

checkベストアンサー

+3

全部はみてないですが、

なぜ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 22:31

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

    キャンセル

  • 2018/01/13 10: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に足しているようなのです。

    そこまではわかりました。もうすぐで答えは出そうです。ありがとうございました!

    キャンセル

  • 2018/01/13 11:31

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

    キャンセル

  • 2018/01/13 11:55

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

    キャンセル

  • 2018/01/13 12:27 編集

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 91.05%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C

    2958questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。