atoi関数のかしこい実装 - yohhoyの日記
C標準ライブラリ Muslのatoi関数実装 では、符号付き整数オーバーフロー回避のため負数範囲で10進数値を減算してゆき最後に符号反転を行っている。 int atoi(const char *s) { int n=0, neg=0; while (isspace(*s)) s++; switch (*s) { case '-': neg=1; case '+': s++; } /* Compute n as a negative number to avoid overflow on INT_MIN */ while (isdigit(*s)) n = 10 * n - (*s++ - '0'); return neg ? n : -n; } C言語の符号付き整数型(int)では “2の補数” 表現が用いられるため*1、最大値INT_MAXより最小値INT_MINの絶対値が 1 だけ大き
C言語入門
はじめに 第1の関門 プログラミングレッスン1 簡単なプログラム 変数を使う よく使うデータ型一覧 ワンポイント〜文字と文字列 計算をしよう よく使う演算子一覧 キーボード入力を受け付ける (scanf) 条件分岐をする (ifとswitch) 繰り返し処理 (forとwhile) break文 goto文 ワンポイント〜文 虫取り教室 コメントアウト printf()デバッグ プログラミングレッスン2 配列変数 多次元配列 関数を作る return文 変数のスコープ ワンポイント〜引数の渡し方 数値処理の達人 数学関数 桁をそろえて表示 乱数 8進数と16進数 最後に 参考文献 Ｃ言語は、（例えばBASICやFortranと比べて）非常に機械に近い非人間的な言語です。よって、コンピュータの内部構造まで教えたくなるのですが、ここではそこをぐっとこらえます。本稿の目標としては、大学の簡単な課
Bal4u : C/UVa
本人が得意としているのはC言語（C++でも，C#でもありません）．数値計算・数論・ソート・検索・計算幾何学・符号・文字列照合等数多くのC言語用ライブラリがここに置いてあります． また，2004年末頃から，スペインにあるオンライン・プログラミング・コンテスト・サイト に参戦していた．参戦記や解答プログラムの一部もここに公開しています． 効率的に約数の個数を求めるアルゴリズムを考えているが、まだ四苦八苦している状態。つまり、1～500万までの整数について、それぞれの約数の数を一気に求めたい。 個々の整数なら、素因数分解して、因数の指数の積で約数の数が分かるのだが、1個1個やっているのでは、遅すぎて話にならない。 それよりも多少高速なプログラムは以下の通り。それでも数秒かかってしまう。 #define MAX 5000000 int c[MAX+10]; /* 約数の数を記録する */ void
Bonanzaで使われているinsertion sortとは何か？ - Bonanzaソース完全解析ブログ
■ Bonanzaで使われているinsertion sortとは何か？ Bonanzaで使われているsort(並べ替え)は、 1) insertion sort 2) shell sort 3) quick sort の3種類である。 3)はCのqsort関数を呼び出しているだけなので解説は不要だろう。また、3)は定跡データベースのメンテナンスにのみ使われており、実際の探索で使われているのは1),2)のみだ。 また、2)には1)が必要である。そこで、今回は1)について解説する。 ■ Bonanzaのnext.c Bonanzaのnext.cは、次の指し手を生成するcoroutineである。ここでinsertion sortが使われている。 指し手生成をcoroutineにしないでいきなり全部の手を生成したり、全部の手に対して点数をつけてquick sortしたりすると劇的なパフォーマンスの
C - でも一番右端の立っているビット位置を求めてみた : 404 Blog Not Found
2009年07月07日03:30 カテゴリMathLightweight Languages C - でも一番右端の立っているビット位置を求めてみた 素晴らしい。 2009-07-04 - 当面C#と.NETな記録 問題の説明はここまでにして、コードの紹介です。Hacker's delight のコードより4〜5倍速く、そして、イミフ加減が半端じゃない！これ一つで 64bit 値以下のすべての値に対応できます。 でも、実際にどれくらい威力があるか試してみたかったのでCに移植してみた。意外な結果が出ております。 0x03F566ED27179461ULL まずは黒魔術。より黒魔術っぽくしてみました。 typedef unsigned long long U64; #define HASH 0x03F566ED27179461ULL static int ntzhash[64]; void i
アルゴリズムの小技
与えられた整数のうち、立っているビット数を数えろ、と言われたらどうします？ 一番最初に思いつくのは、ビットシフトしていって0になるまで数えるという、素直なやり方でしょう。 例えばこんな感じ。 int bitcount(unsigned long n) { for (int c = 0; n; n >>= 1) { if (n & 1) { ++c; } } return c; } 間違ってはいないけど、なんとなく遅そう。 テーブルを使えばもっと速い。 int bitcount(unsigned long n) { const static unsigned char aa[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; for (int c = 0; n; n >>= 4) { c += aa[n & 0xf]; } retu
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.sat.t.u-tokyo.ac.jp/~omi/random_variables_generation.html