การบรรจุเซตที่ไม่ยกกำลังของจำนวนเต็ม 2 จำนวน

ฉันมีชุดของจำนวนเต็ม ซึ่งแต่ละชุดมีช่วงเฉพาะ:

foo = [1, 5]
bar = [1, 10]
baz = [1, 200]

ฉันสามารถคำนวณได้ว่าต้องใช้จำนวนบิตเท่าใดในการจัดเก็บแต่ละหมายเลขแยกกัน ตามจำนวนสถานะที่แตกต่างกันที่ตัวเลขเหล่านั้นสามารถมีได้:

foo = 5 possible states   ~ 3 bits
bar = 10 possible states  ~ 4 bits
baz = 200 possible states ~ 8 bits

ซึ่งให้ฉันทั้งหมด 15 บิต แต่ทุกหมายเลขก็มีช่วงที่ไม่ได้ใช้ทำให้เปลืองพื้นที่ ฉันสามารถคำนวณบิตที่จำเป็นสำหรับทั้งชุดแทนได้โดยการคำนวณสถานะที่เป็นไปได้ทั้งหมดของตัวเลขทั้งหมดที่รวมกัน:

5 * 10 * 200 = 10000 possible states ~ 14 bits

นี่สามารถช่วยฉันได้นิดหน่อย!

และนี่คือที่มาของคำถามของฉัน: วิธีใดที่ดีที่สุดในการโหลดและจัดเก็บหมายเลขโดยใช้เค้าโครงประเภทนี้


person Rick de Water    schedule 22.05.2018    source แหล่งที่มา


คำตอบ (1)


รายการตัวแปรที่มีช่วงต่างกันดังนี้:

foo = [1, 5]
bar = [1, 10]
baz = [1, 200]

(เกือบ?) สามารถตีความได้ว่าเป็นการแสดงจำนวนฐานผสม หากพวกมันเริ่มต้นจากศูนย์ การโต้ตอบจะเกิดขึ้นทันที แต่เนื่องจากสิ่งเหล่านี้เริ่มต้นที่หนึ่ง (หรือโดยทั่วไป: หากพวกมันเป็นชุดความเป็นไปได้ ใดๆ ที่มีอยู่จำกัด) พวกเขาจะต้องถูกแมปใหม่เล็กน้อยก่อน ที่นี่เพียงลบออก อันหนึ่งสำหรับการแปลงเป็นสถานะ "บรรจุแล้ว" และเพิ่มกลับเมื่อถอดรหัสอีกครั้ง

การเข้ารหัสนั้นดีและง่าย โดยเกี่ยวข้องกับการดำเนินการราคาถูกเท่านั้น:

packed = (foo - 1) + 5 * (bar - 1) + (5 * 10) * (baz - 1)

ปัจจัยขนาดมาจากจำนวนสถานะที่เป็นไปได้แน่นอน ทุกองค์ประกอบจะต้องได้รับการแมปใหม่ในช่วงที่อยู่ติดกันโดยเริ่มต้นที่ศูนย์ จากนั้นจึงปรับขนาดด้วยผลคูณของ #state ขององค์ประกอบก่อนหน้า โดยองค์ประกอบแรกจะถูกปรับขนาดด้วย 1 (ผลคูณว่าง) โปรดทราบว่า [1 .. 5] มี 5 สถานะ ไม่ใช่ 4

การถอดรหัสเกี่ยวข้องกับเศษและการหาร วิธีที่ง่ายที่สุด (แต่โดยทั่วไปไม่ใช่วิธีที่เร็วที่สุด) คือการแยกตัวเลขทีละหลัก:

// extract foo
foo = packed % 5 + 1
// drop foo from packed representation
packed /= 5
// extract bar (which is now the lowest digit in 'packed')
bar = packed % 10 + 1
// drop bar
packed /= 10
// top digit is left over
baz = packed + 1

สำหรับตัวอย่างที่ใหญ่กว่า จะมีประสิทธิภาพมากกว่าในการ "สับ" หมายเลขที่บรรจุออกเป็นส่วนๆ แยกกันสองสามส่วนก่อน แล้วจึงถอดรหัสแยกกัน วิธีนี้จะป้องกันไม่ให้มีการดำเนินการที่ต้องพึ่งพากันเป็นลูกโซ่ยาว ซึ่งวิธีแบบเลขต่อหลักจะส่งผลตามธรรมชาติ

การทำงานโดยตรงกับการแสดงที่อัดแน่นโดยทั่วไปนั้นยุ่งยาก ยกเว้นการเพิ่มและลบออกจากองค์ประกอบ หาก คุณรู้ว่าจะไม่ล้น

person harold    schedule 22.05.2018