C言語なら俺に聞け 153

2019/08/17(土) 23:02:42.00

C言語の話題のみ取り扱います C++の話題はC++スレへ
質問には最低限の情報(ソース/コンパイラ/OS)を付ける
数行で収まらないソースは以下を適当に使ってURLを晒す
https://paiza.io/
https://ideone.com/
http://codepad.org/

C11
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf

C99
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf
http://kikakurui.com/x3/X3010-2003-01.html

C FAQ 日本語訳
http://www.kouno.jp/home/c_faq/

JPCERT C コーディングスタンダード
https://www.jpcert.or.jp/sc-rules/
-
VIPQ2_EXTDAT: checked:vvvvv:1000:512:----: EXT was configured
※前スレ
C言語なら俺に聞け 152
https://mevius.5ch.net/test/read.cgi/tech/1560763630/

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2019/12/02(月) 09:05:35.78

>>435
みんな大学の課題という前提を忘れて実務的実用的な話になってるよね
フーリエ変換と逆変換をプログラムで実装できているかが採点基準であって
画像はバイナリデータがちゃんと元に戻っているか確認する手段にすぎないと思う

2019/12/02(月) 13:14:43.06

圧縮って書いてあるんだからバイナリ一致しなくてもいいのでは？
同じ絵っていうのはパッと見同じってことじゃなくて？

2019/12/02(月) 13:29:01.68

可逆圧縮か不可逆圧縮か

2019/12/02(月) 13:30:39.72

不可逆でフーリエ変換？

2019/12/02(月) 13:30:57.35

逆だ

可逆でフーリエ変換？

2019/12/02(月) 13:33:14.63

隣接ピクセル間隔より狭い高調波は不要だから有限の離散フーリエ変換でも
実質可逆とみていいんだよね？　（符号化による情報落ちを考慮しない話）

2019/12/02(月) 14:34:46.17

フーリエは本来可逆だ。

2019/12/02(月) 14:52:09.59

圧縮が目的でフーリエ変換するのに
何も情報を減らさずにそのまま戻してどうする？

2019/12/02(月) 14:53:09.69

>>441
心配しなくても
ナイキスト周波数を越える成分はフーリエ変換の結果には含まれない

2019/12/02(月) 14:56:19.28

>>423
>>426
離散コサイン変換じゃいかんのか

2019/12/02(月) 14:59:03.83

>>432
どうせ課題なんだしそこまで求めてないというか
もしすごいのが出来たら教授が自分の成果にして発表するんやろ

2019/12/02(月) 15:03:30.60

>>442
ほんそれ

ただし無限な

2019/12/02(月) 15:04:01.88

スゴイの出来たら、先に特許申請だな

2019/12/02(月) 15:06:19.88

講義での学習課題としては非圧縮でないと判定が面倒だな
単にデータを間引いただけなのか演算を間違っているのか確認に手間が掛かる
むしろ完全可逆で実装した方が採点する側としては分かりやすいだろう
出題者の意図はどこにあるか質問者は理解しているのだろうか？

2019/12/02(月) 15:16:11.81

なんで理解しなきゃいけねーの
そういう旨なら文章にハッキリ書いてくれねーと困るワケ
お気持ちを察せよ　なんてのが罷り通る案件なの？

2019/12/02(月) 15:18:11.07

「オメーの気持ちなんてしったこっちゃねー
　オレに分かるように話せ」
が今の潮流

分からないように反為さないヤツは無視していいし排除していい
なんつったってオレが理解出来ないヤツは何言ってるか分からないコミュニケーション不可能な敵に近いからな
気持ち悪いから排除してもいいし、何よりオレに理解されようと思ってない
だから排除していいでしょ

……という思考で動くのが現代の日本社会

2019/12/02(月) 15:21:55.25

いやクライアントの意向を無視して好き勝手やっていたら仕事干されるだろ

2019/12/02(月) 16:43:27.43

保存とは書かれているが圧縮とはどこにも書かれてない件

2019/12/02(月) 16:47:13.54

てか皆さん「フーリエ変換くらい当然知ってる」って雰囲気なのが凄いわ。

2019/12/02(月) 17:56:06.03

>>453
>>425,426

2019/12/02(月) 18:01:01.74

圧縮しないなら
保存でフーリエ変換使う意味がわからんがな

2019/12/02(月) 18:04:51.11

フーリエ変換そのものは理系の大学卒であれば誰でも知ってる
具体的な数値計算のアルゴリズムを知っているかはその人の専門分野による

2019/12/02(月) 18:35:35.76

理系でも生物系なら触りもせん

2019/12/02(月) 18:53:16.42

専門課程ではなくても一般教養の数学系の講義で学んでると思うけど

2019/12/02(月) 19:00:10.22

微積と線形代数ぐらいで触らんかったぞ
大学なんか講師次第だからなあ

2019/12/02(月) 19:09:01.78

文系だと無いと思うな
統計学や代数幾何、微積分
この辺まで

2019/12/02(月) 19:11:47.56

はるか前なので忘れたが、大学ではフーリエ級数って名前だった希ガス

2019/12/02(月) 19:12:24.77

理系の大学卒だが
フーリエ変換を大学で習った記憶はないなあ
覚えてないだけかな？

2019/12/02(月) 19:40:44.78

フーリエ変換はフーリエ級数展開の一般化
フーリエ級数展開の基本周期を無限大まで拡大すると周波数成分は離散から連続となる
要するに周波数成分を連続スペクトルとして扱うのがフーリエ変換

2019/12/03(火) 19:46:15.44

画像のフーリエ変換なんてどうやってやるんだ？って思ってググったら結構面白いな
ちょっと実装してみよう
https://algorithm.joho.info/image-processing/fourier-transform/

2019/12/03(火) 22:43:48.90

数学科院卒だがフーリエ変換には掠りもしてない
工学部の一部しか触ってないだろう

2019/12/04(水) 02:04:25.88

数学的には解析学の領域
どちらかといえば数学と物理の境界
電気工学や情報工学では必須
https://ja.wikipedia.org/wiki/%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B

2019/12/04(水) 02:24:25.40

工学部では厳密な理論よりも応用が重要なので表面的な触りだけで深入りはしない
厳密な議論はやはり数学者の分野だと思う

2019/12/04(水) 09:27:46.76

画像処理はOpenCVとかで済ましちゃうから細かい数式は気にしない

2019/12/04(水) 09:38:25.43

それには同意
フーリエ変換の利用にはFFTの概要だけ理解していれば十分
ただ数学の専門家が掠りもしてないというのは如何なものかとは思う

2019/12/04(水) 10:58:24.04

Wikipedia繋がりでFFTのリンク開いてみるとVisualBasicでの実装例が掲載されてるね
https://ja.wikipedia.org/wiki/%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B

2019/12/04(水) 13:12:26.50

>>468
数学的にはとっくの昔に解決してるから
あとは工学系の仕事

2019/12/04(水) 13:15:06.38

>>470
応用数学とかそういう分野ならまだしも
純粋な数学者はそんなことには興味がない

2019/12/04(水) 13:17:30.35

FFTはアルゴリズムの名前

2019/12/04(水) 13:33:37.43

ラプラス変換やz変換あたりだと完全に工学分野だけどフーリエ変換くらい汎用なものは数学分野でも活用されてると思うけどね
フーリエ級数はローラン級数などと同じ複素解析の基本的な考え方でしょ
べきに展開するか指数に展開するかの違いくらいのもの

2019/12/04(水) 13:59:41.66

>>475
>>472

2019/12/04(水) 14:02:42.65

無理を言ってはいけない
数学者には楽器は作れても名曲を作る事はできない

2019/12/04(水) 15:03:29.21

名曲を作るのは数学者でも物理学者でも工学博士でもない
発明家や企業だ

2019/12/04(水) 21:02:14.66

沖縄音階は適当にランダムに音出しても曲に聞こえちゃうけどな

2019/12/04(水) 22:00:13.57

>>479
それは沖縄音階に馴染みがないから、沖縄音階が使われているだけで沖縄っぽいと感じてるだけなんじゃないかな？
沖縄の人からしたら、そんなデタラメでは曲として成り立ってないと思わないのかな。

2019/12/05(木) 00:53:08.83

そういった抽象的な感覚を数値化して扱うための手段がフーリエ解析やスペクトル解析と呼ばれる分野
音楽の音階(周波数)やリズム(時系列)を分解して客観的に評価するのが科学的なアプローチ

2019/12/05(木) 03:51:45.82

>>481
どちらかといえばウェーブレット解析の方が適しているような気がする
フーリエ変換では周波数特性を求める際に時間領域の情報は失われる
https://ja.wikipedia.org/wiki/%E3%82%A6%E3%82%A7%E3%83%BC%E3%83%96%E3%83%AC%E3%83%83%E3%83%88%E5%A4%89%E6%8F%9B

プログラムで扱うなら離散ウェーブレット変換
https://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%82%A6%E3%82%A7%E3%83%BC%E3%83%96%E3%83%AC%E3%83%83%E3%83%88%E5%A4%89%E6%8F%9B

2019/12/05(木) 07:07:45.12

確かにフーリエ解析では周波数成分の変化の時系列データを扱うのは難しい
少し浅はかだったなすまん
それにしても数学者が理論を確立して証明しそれをベースに開発が進むという典型例だな

2019/12/05(木) 11:04:28.35

200年くらいかかってるな
ベイズで100年ちょっとか

2019/12/05(木) 12:56:44.93

>>480
さあ？まあ、実際にやってみな。自分でピアノやオルガンのキーを沖縄音階で適当に押すだけでわかる。

2019/12/05(木) 13:09:00.01

自分で弾いたら曲になるように弾いちゃうからランダムじゃない
本当にランダムで弾いたら曲にならない

2019/12/05(木) 13:51:21.95

ム板ならそれらしくランダムに演奏するソフトうｐ汁
https://www.youtube.com/watch?v=5dsFqZf8owg

2019/12/05(木) 15:14:54.84

糞曲に興味はない

2019/12/05(木) 23:45:36.26

質問失礼いたします。
以下のpopcountは引数xを2進数で表したときの1の数を返す関数なのですが、
動作原理がよく理解できないため考え方のヒントなどをいただけないでしょうか。

int popcount(unsigned long long x)
{
　　x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
　　x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
　　return (int)(((x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f)) % 0xff);
}

以下のpopcount2は自分で作ったもので、これならうまくいくことは分かるのですが、
上のpopcountも本質的には同じことをやっていると考えていいものなのでしょうか。

int popcount2(unsigned long long x)
{
　　int n = 0;
　　for (int i = 0; i < 64; i++)
　　{
　　　　if ((x & 1ull << i) != 0ull)
　　　　{
　　　　　　n++;
　　　　}
　　}
　　return n;
}

どうぞよろしくお願いいたします。

2019/12/05(木) 23:51:53.81

https://ideone.com/8LfIh0
こんにちは。
ちょっと思いついたので、こういうコードを書いたのですが、
普段からreallocを使わないのでこのコードがあっているか解らないのです。
これで大丈夫ですか？

2019/12/06(金) 00:02:45.40

>>490
reallocが成功した場合古いポインタに対してfreeは呼ばなくていいと思いますよ。
reallocの戻り値は古いポインタと異なるものになる保証はないはずなので、
freeを呼んでしまうとせっかくreallocした領域まで解放されてしまうかも。

2019/12/06(金) 00:04:45.19

>>491
了解です。ありがとうございました。

2019/12/06(金) 00:12:50.26

>>492
ちゃんとコードを読んだら↓の部分はケアされてましたね。失礼しました。
> reallocの戻り値は古いポインタと異なるものになる保証はないはずなので、

ただ、reallocが成功したらfreeは呼ばなくていいのは間違いないと思います。

2019/12/06(金) 00:50:56.12

>>490 のreallocのコード返り値のポインタが不定を指しているので、使わないでください。
こっちを使ってください。
https://qiita.com/yakitori32/items/98256db666029fb5ebca

2019/12/06(金) 00:55:18.93

>>493
了解です。ありがとうございます。

2019/12/06(金) 01:07:01.79

>>489
超高速ビットカウント
でググって出てくるページでちゃんと解説してくれてる
この手のよく見るやつはちょっとググれば解説見つかる

何を本質と置くかによるけど両者はそもそもアルゴリズムが違うのでその観点からなら違う
どちらのコードも結果は同じでも前者のほうが圧倒的に処理速度が早い
ビット数などが必要になる処理では速度が重要になるケースも多々あるので結果が同じでも後者は使い物にならない場合もある

2019/12/06(金) 01:36:02.35

>>496
レスありがとうございます。紹介していただいた記事を読ませていただき、大変勉強になりました。

ただ、>>489 の場合だと「ビットカウントするデータ列がある程度長い場合」には
当てはまらないため記事の前半の内容がアルゴリズムの基本になるとか思うのですが、
私が理解した範囲で記事の内容を参考にして関数を作成しても以下のようにしかできませんでした。

int popcount(unsigned long long x)
{
　　x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
　　x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
　　x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f);
　　x = (x & 0x00ff00ff00ff00ff) + (x >> 8 & 0x00ff00ff00ff00ff);
　　x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff);
　　return (int)((x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff));
}

しかし >>489 の関数はこれを途中で打ち切って % 0xff をくっつけたような形になっており、
やはり完全な理解には至っていない状況です。
もし可能であれば、この部分についてもヒントをいただけると大変嬉しく思います。
たびたび申し訳ありませんが、どうぞよろしくお願いいたします。

2019/12/06(金) 04:41:11.15

>>497
64ビット長のビットカウントの最大値はたかだか64なので8ビット(最大255)で表現できる
一方、64ビットデータの分割統治による畳み込み計算は1回目で2ビット×32組、2回目で4ビット×16組、3回目で8ビット×8組の結果が得られる
ビット数を求めるだけなら3回目の結果が得られた時点で8ビットの最大数(255)で3回目の畳み込み結果の剰余を求めてやればそれぞれの組の重み(ビット数)が計算できる
(64を超えることはないことが明らかなので)

2019/12/06(金) 04:45:05.84

訂正
それぞれの組の重みの総計(ビット数)

2019/12/06(金) 05:11:25.02

>>498
わかりやすいご説明どうもありがとうございます！ほぼ理解できたと思います。
たとえば十進数の123を十進数文字の最大値9で割った余りは
1+2+3と等しくなりますが、これと同じ原理ということですよね？

ただよくよく考えてみると、そもそも十進数の各桁の合計を9で割った余りが
元の数を9で割った余りと等しくなることについても
お恥ずかしながら豆知識として知っているだけで原理を理解できていませんでした。
ただこれに関してはもはやC言語ではなく算数の問題なので、
その方面の解説サイトをググって勉強しようと思います。
なにはともあれ、回答してくださった皆様方、どうもありがとうございました。

>>495
読みやすい記事を提供してくださっているので、もう少しだけコメントさせてください。

現状だと、MemoryReAllocateを呼び出す側は関数の成否を確認するために
Mem->Memoryを覚えておく必要がありますので、MemoryReAllocateの引数に
参照渡しを使われるならMemoryReAllocateの戻り値はMomeryではなくて
成否を表すboolなどにされてはいかがでしょうか。

また、reallocは第一引数としてNULLを許容しているので
MemoryReAllocateは入力のMem->MemoryがNULLであっても
Mem->ElementSizeが正しい値であれば正常に動作しますが、
その一方でMemoryAllocateは失敗するとElementSizeがゼロの構造体を
返すので少しアンバランスかなと思いました。

あと、MemoryFreeがboolを返すのであれば、freeの前にNULLチェックを入れて
その結果をMemoryFreeの戻り値としてもいいかなと思いました。
（free関数自体はNULLを渡しても何もしないだけで問題は起こりませんが）

以上お目汚し失礼しました

2019/12/06(金) 05:15:04.10

1回進むごとに
2bitずつに区切って、1の数を各2bitに入れる
4bitずつに区切って、1の数を各4bitに入れる
8bitずつに区切って、1の数を各8bitに入れる
...

となるので
>>489だと各バイトの1の合計が、各バイトに入る

各バイトなので256バイトのテーブルを使う方法もある
チープなCPUだとこちらの方が速い

逆にリッチなCPUだと数える命令が最初から備わってたりするしベクタ化も可能

Icelake以降だとAVX512VBMIの命令を使って
超高速に64バイト分カウント出来る

2019/12/06(金) 05:24:05.53

>>500前半
なんか違う

10進数の各桁に関しては
1000a+100b+10c+d
=999a+99b+9c+a+b+c+d
=9(111a+11b+c)+(a+b+c+d)

これを2進数でやると
9のところが1になるからあまり意味がない

2019/12/06(金) 05:33:31.46

分割統治っていうより
レジスタ内の桁数を使ってSIMD演算してるって感じ

01020304 + 02040608

2桁ずつの4個の足し算になってるでしょ？

2019/12/06(金) 05:47:57.81

vpsrld
vpermb
vpermb
vpaddb

AVX512VBMIを使うと
レジスタに値がある状態で
4命令で64バイト分

2019/12/06(金) 05:56:22.53

>>501 >>504
レスありがとうございます。

> 各バイトなので256バイトのテーブルを使う方法もある
確かにある程度のビット幅ごとにテーブルを使って計算する方法は
シンプルですが効果が高そうですね。

> 逆にリッチなCPUだと数える命令が最初から備わってたりするしベクタ化も可能
> 4命令で64バイト分
勉強になります。本当に速さが必要ならCPU自体の理解から始めるべきなんですね。
このあたりのハードウェアの違いは標準ライブラリ関数が吸収してくれると最高なのですがｗ

>>502
10進数の話の数式どうもありがとうございます！大変勉強になりました。

そうすると、>>489 の popcount の最後にやっているのは
2進数というか0x100進数で、

0x1000000*a+0x10000f*b+0x100*c+d
=0xffffff*a+0xffff*b+0xff*c+a+b+c+d
=0xff*(0x01010x*a+0x0101*b+c)+(a+b+c+d)

ということになると思うのですがいかがでしょうか。

2019/12/06(金) 05:58:37.54

>>505 の数式が変でした。正しくは以下のとおりです。失礼しました。

0x1000000*a+0x10000*b+0x100*c+d
=0xffffff*a+0xffff*b+0xff*c+a+b+c+d
=0xff*(0x010101x*a+0x0101*b+c)+(a+b+c+d)

2019/12/06(金) 06:20:08.91

最後の % 0xff を見てなかった
なので各バイトの1の個数と勘違いしてました

>>506はその通り

%は、除算命令を使うと遅いので
コンパイラは
0x0101010101010101
との乗算とシフトに置き換えそうです

PCの64bit環境だとPOPCNT命令がそのまま1命令
Icelake以降だとVPOPCNTQで8個を1命令
で出来ます

2019/12/06(金) 06:24:24.02

x % 0xff
よりは
x * 0x0101010101010101 >> 56 & 0xff
の方が直接的でコンパイラを頼らない記述でしょう

2019/12/06(金) 06:34:20.70

それだと
剰余 x % 0xff
ではなくて
商 x / 0xff

2019/12/06(金) 06:36:33.62

>>508 で大丈夫
乗算の筆算を考えてみよう

2019/12/06(金) 06:37:31.16

>>507-508
レスありがとうございます。

> x % 0xff
> よりは
> x * 0x0101010101010101 >> 56 & 0xff
> の方が直接的でコンパイラを頼らない記述でしょう
コンパイラの最適化によって一行目が三行目に
置き換えられる可能性があるということですか！？
難しそうですがちょっと考えてみたいと思います。

> PCの64bit環境だとPOPCNT命令がそのまま1命令
> Icelake以降だとVPOPCNTQで8個を1命令
本当に速度を求めるならCPUの命令を直接使えということですね。
覚えておきます。

2019/12/06(金) 06:42:08.81

>>511
コンパイラは普通、定数の除算は乗算に置き換えます
乗算、シフトは1クロック、除算は数十クロックかかるのが普通なので

ただ、
>>508 にまでは最適化されないかも
なので>>508の方が良いです

2019/12/06(金) 06:54:43.75

>>512
ありがとうございます。そのようにしたいと思います。

ご親切に甘えてしまい申し訳ないのですが、
もう一つ質問させてください。今、
① = x % 0xff
と
② = x * 0x0101010101010101 >> 56 & 0xff
について考えていたのですが、
x = 0xff のとき、
① = 0x00, ② = 0xffのように、別の値になりませんか？
これは、どこか書き間違いがあるとういことでしょうか。
それとも、この違いは今回の用途では問題にならないということでしょうか。

2019/12/06(金) 06:57:32.55

>>512
立て続けにすみません。。。たった今理解しました。
「この違いは今回の用途では問題にならない」が正解ですね。

2019/12/06(金) 06:57:55.91

除算命令、
Skylakeで最大90クロックだそうで...
簡単な命令だと1クロックで3～4個実行出来る事を考えると劇遅ですね

Icelakeだと18クロックなので
改善されてるみたい

2019/12/06(金) 07:06:52.23

>>515
> 除算命令、
> Skylakeで最大90クロックだそうで...
なんと！しかも、「最大」という表現が付くんですね。
つまり、ただの数値計算なのに
クロックの数がデータに依存する可能があるということ…？

2019/12/06(金) 07:12:58.28

>>516
除算命令の実行時間はデータに依存します
内部的にループしてるようなものなので

SIMDの除算は多分一定
Icelakeももしかしたら一定かもしれません

SIMD乗算も非常に小さな値だと遅い事があったような

2019/12/06(金) 07:35:33.29

>>517
小さい値だと遅い！？
すみません、ハードウェアの知識がなさすぎて
タイプミスをされたのか本当にそうなのかの判断すらつかないです。。。

2019/12/06(金) 07:55:08.53

https://ja.m.wikipedia.org/wiki/%E9%9D%9E%E6%AD%A3%E8%A6%8F%E5%8C%96%E6%95%B0

ここの｢性能問題｣参照
浮動小数点演算の話ですので今回は関係ないです

2019/12/06(金) 07:59:35.87

そりゃ並列処理できるような相互依存性の低い大量のデータでもあるならともかく
小さなデータ塊対象だとパック化やアンパック化する手間が掛かる分だけ
総合的にはSIMD使った方が遅くなるだろ
馬鹿となんとかは使いようと言うだろ

2019/12/06(金) 08:10:43.32

どこの誤爆か気になる

2019/12/06(金) 12:19:42.67

>>520
馬鹿がSIMD使うと遅くなる
それはそうかも

2019/12/06(金) 15:17:31.13

>>519
勉強になります。
非正規化数という言葉はちらっと聞いたことはありますが、こういうデメリットもあるんですね。
そして、それでも非正規化数を使うのは
「浮動小数点数の加減算は決して『アンダーフローによるゼロ』にならない」
という理由があるのだということも初めて知り、とても興味深く感じました。

ところで、ビット演算に関してもう一つ相談させていただいてもよろしいでしょうか。

動的メモリ再確保のコストを減らすために確保するメモリのサイズを必ず 2ⁿ-1 の形にしたくて、
与えられた数を下回らない最小の 2ⁿ-1 の値の値を返すような関数を作って使っています。
つまり引数xを2進数で表したときの一番上位の1以下をすべて1に置き換えるような関数で、
具体的には以下のように記述しています。

int fill_lower_bits(int x)
{
　　x |= x >> 1;
　　x |= x >> 2;
　　x |= x >> 4;
　　x |= x >> 8;
　　x |= x >> 16;
　　return x;
}

この関数は割と使用頻度が高いので、PCの64bit環境にPOPCNT命令があるように、
もしfill_lower_bitsと似た振る舞いをする命令があれば名前を教えていただけないでしょうか。

（続く）

2019/12/06(金) 15:18:25.28

（続き）
また、こちらはあまり使い道は思いつきませんが、

int fill_higher_bits(int x)
{
　　x |= x << 1;
　　x |= x << 2;
　　x |= x << 4;
　　x |= x << 8;
　　x |= x << 16;
　　return x;
}

という関数を考えることもできて、これなら

int fill_higher_bits(int x)
{
　　return -(x & -x);
}

のように簡単な書き方に変更できます。
fill_lower_bitsについてもこういうテクニックがあればいいなと思っているのですが、
もし何かご存知であれば教えていただけると嬉しいです。

2019/12/06(金) 19:09:08.62

>>523
BSR命令といくつかの命令を組み合わせて出来ます
Cからだと _BitScanReverse64

>>524
x | -x
の方が良いと思います

2019/12/06(金) 19:33:49.52

>>525
何度も本当にどうもありがとうございます。大変勉強になります。

> _BitScanReverse64
こんな命令があったとは！
この名前で検索したら、今まで知らなかった興味深いページがたくさんヒットしました。
ReverseじゃなくてForwardというのもあるみたいですが、
Forwardの方はマイナスを使う方法でも十分高速になりそうなので、
どちらが速いか検証してみようと思います。

> x | -x
確かに…。
ド・モルガンの法則で ~(x & ~x) が ~x & x に書き換えられるのはすぐに分かるのですが、
もしかしてそれと同じことがマイナスでもできるのでしょうか。
-x が ~x + 1 と同じになることは理解しているので、ちょっと考えてみたいと思います。

2019/12/06(金) 19:53:04.32

>>526
> ド・モルガンの法則

-(a & b) = -a | -b が成り立つかなと期待したのですが、
a = 0, b = 1 のときにつまずいてしまいました。

でも、>>525 に書いていただいた -(x & -x) = -x | x は間違いなさそうです。

こういう式の変形って、どこかテキストに載っていたりするのでしょうか。

2019/12/06(金) 20:51:24.53

自分で頑張って探すんです

~x
x-1
-x
&
|
^

これらを組み合わせれば
一番右のビット関連がいろいろと出来ます

???10000
に対して
11110000
11100000
00010000
00011111
00001111
これらを得る最小回数の演算を考えてみてください

2019/12/06(金) 21:03:52.43

ド・モルガンと似た問題で、
「君たち2人は注意されないならば、君たち2人は私語を止めない」
の対偶、
「君たち2人が私語を止めるならば、君たち2人は注意される」
って矛盾にちょっと考えてしまったわ。

2019/12/06(金) 21:07:30.59

x 注意される
o 注意された

2019/12/06(金) 21:15:00.21

>>530
さすが、その通り。

2019/12/06(金) 23:44:25.67

>>523
メモリ確保やアクセスの時間に比べれば
サイズ計算の時間は無視出来る

ビット演算の趣味として楽しむ分には良いけど
普通にループでもパフォーマンスは変わらない

パフォーマンスが重要じゃないところ
(つまりほとんどの部分)は
移植性、見やすさ、工数、...
などが優先される

ということは知っておいた方が良いですね

2019/12/06(金) 23:51:44.77

分野によってはループや比較による分岐は遅すぎて使えないなんてことままあるよ

2019/12/07(土) 00:10:26.85

>>523の話

2019/12/07(土) 00:10:27.55

それは経験談？
それとも誰かからの受け売り？