PTT數位生活區 / C_and_CPP (C/C++)

Re: [問題] 在一個給予的mask中，例舉所有k-bit 組合

看板C_and_CPP (C/C++)作者 (舞秋風 憶白雲)時間9月前 (2024/02/05 12:23), 9月前編輯推噓2(2推 0噓 6→)
留言8則, 5人參與, 9月前最新討論串3/3 (看更多)
謝謝各位大神的建議，我現在可以用到Gosper's Hackw產生我需要的bit組合。 我現在有個更進階的問題。 我想要根據1 bit的count來排例n bits的數字，但不用sorting。 舉例，當n=3時。我希望數字排例如下。當我要讀第4個數字時，我會拿到3。 1, 2, 4, "3", 5, 6, 7 [001, 010, 100, 011, 101, 110, 111] Code 可能如下。 unsigned x = get_kth_number_by_count_of_1_bits(k /*4*/, numer_of_bits /*3*/); 我現在是用gosper hackw先產生一個look up table。 但我希望可以不用look up table，直接透過bit operation或數學運算， 在constant time，拿到我所要的數字。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 211.21.176.170 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1707107012.A.8E6.html ※ 編輯: dnol (211.21.176.170 臺灣), 02/05/2024 12:29:34
→
02/05 13:48, 9月前 , 1F
look up 不好嗎 空間限制有這麼嚴格?
02/05 13:48, 1F
→
02/05 14:09, 9月前 , 2F
我目前是在cuda上做平均運算，所以對空間和時間比較要求
02/05 14:09, 2F
→
02/05 15:49, 9月前 , 3F
CUDA 有直接數幾個 1 幾個 0 的 function
02/05 15:49, 3F
推
02/06 03:08, 9月前 , 4F
可以研究一下 Combinatorial number system
02/06 03:08, 4F
→
02/06 13:42, 9月前 , 5F
謝謝樓上的提示。
02/06 13:42, 5F
推
02/06 16:46, 9月前 , 6F
02/06 16:46, 6F
→
02/06 16:47, 9月前 , 7F
對小的nk來說查表還是比較快，所以要看你資料分佈
02/06 16:47, 7F
→
02/06 16:48, 9月前 , 8F
記得leetcode有一題就是考O(1)
02/06 16:48, 8F
‣ 更多 dnol 的文章
文章代碼(AID): #1bm6B4Zc (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 dnol 的文章
文章代碼(AID): #1bm6B4Zc (C_and_CPP)