[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
964(1): デフォルトの名無しさん [sage] 2023/07/21(金) 07:58:12.84 ID:XtiUJMX6(1/2) AAS
>>927927(7): 蟻人間 ◆T6xkBnTXz7B0 [sage] 2023/07/13(木) 21:54:33.63 ID:pFytGTyV(1/2) AAS
お題: 入力として32ビット整数のビットマスクが与えられる。
ビットマスクに含まれる有効なビットの組み合わせをブルートフォースせよ。
例)
0x13
→(0x1, 0x2, 0x3, 0x10, 0x11, 0x12, 0x13).
0x45
→(0x1, 0x4, 0x5, 0x40, 0x41, 0x44, 0x45).
0x92C
→？？？
Rust
fn foo(input: u32) -> impl Iterator<Item = u32> {
(0..=input).filter(move |n| n & input == *n)
}
ただしこれではループがO(n)
ループをO(log N)にするならこちら
fn foo(input: u32) -> impl Iterator<Item = u32> {
let table: Vec<u32> = bits_iter(input).map(|p| 1 << p).collect();
(0..(1 << table.len())).map(move |bits| bits_iter(bits).map(|p| table[p as usize]).sum())
}
補助bitsイテレータ
fn bits_iter(n: u32) -> impl Iterator<Item = u32> {
let mut n = n;
std::iter::from_fn(move || {
(n != 0).then(|| {
let p = n.trailing_zeros();
n &= !(1 << p);
p
})
})
}
965: デフォルトの名無しさん [sage] 2023/07/21(金) 08:19:47.60 ID:XtiUJMX6(2/2) AAS
>>964
rustfmtがギリギリ2行にまとめてしまうが見にくいので手動で以下へ補正
(改行の違いだけでコード自体は同じです)
fn foo(input: u32) -> impl Iterator<Item = u32> {
let table: Vec<u32> = bits_iter(input)
.map(|p| 1 << p)
.collect();
(0..(1 << table.len()))
.map(move |bits| {
bits_iter(bits)
.map(|p| table[p as usize])
.sum()
})
}
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.053s