Sum Over Subsets Dynamic Programming to Count K-Bits of AND Bitwise Operation Results.
Saved in:
| Title: | Sum Over Subsets Dynamic Programming to Count K-Bits of AND Bitwise Operation Results. |
|---|---|
| Authors: | Soelaiman, Rully1 rully130270@gmail.com, Samsico, Alexander Weynard2 samsicoweynard@gmail.com, Purwananto, Yudhi1 purwananto@gmail.com |
| Source: | IAENG International Journal of Computer Science. Apr2026, Vol. 53 Issue 4, p1343-1357. 15p. |
| Subjects: | Dynamic programming, Binary operations, Binary number system, Computational complexity, Algorithms |
| Abstract: | Bitwise is a fundamental concept in computer science, involving specialized operations for handling logical calculations on binary numbers. One commonly used bitwise operation is AND, where if two binary bits are compared and both are 1, the result is 1. One of the problems is AND Queries, where we have to calculate by using the array A, in every query, how many results when an integer from array A & V has a result of K 1-bit in binary form. This problem has an array A with size N and Q queries. In this paper, we propose a novel solution for the AND Queries problem using Sum Over Subsets Dynamic Programming. Sum Over Subsets Dynamic Programming is a branch of Bitmask Dynamic Programming that utilizes subsets of numbers in a set to find the sum of subsets, aiding in solving the case study of AND Queries are a technique used to calculate the sum of values for all subsets of a given set or bitmask. By using this technique, the solution strategy begins with accepting inputs, identifying subproblems, and grouping subsets, modeling dynamic programming, and substitution using Sum Over Subsets, and Dynamic programming to derive the final result. Based on the experimental testing result, the solution using the Sum Over Subsets Dynamic Programming algorithm requires an average time of 1.121 seconds, which is nine times faster than the time needed, and a constant memory of 12 MB, which uses 0.05% of the required memory limit. [ABSTRACT FROM AUTHOR] |
| Copyright of IAENG International Journal of Computer Science is the property of International Association of Engineers (IAENG) and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 192720771 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Sum Over Subsets Dynamic Programming to Count K-Bits of AND Bitwise Operation Results. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Soelaiman%2C+Rully%22">Soelaiman, Rully</searchLink><relatesTo>1</relatesTo><i> rully130270@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Samsico%2C+Alexander+Weynard%22">Samsico, Alexander Weynard</searchLink><relatesTo>2</relatesTo><i> samsicoweynard@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Purwananto%2C+Yudhi%22">Purwananto, Yudhi</searchLink><relatesTo>1</relatesTo><i> purwananto@gmail.com</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IAENG+International+Journal+of+Computer+Science%22">IAENG International Journal of Computer Science</searchLink>. Apr2026, Vol. 53 Issue 4, p1343-1357. 15p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Dynamic+programming%22">Dynamic programming</searchLink><br /><searchLink fieldCode="DE" term="%22Binary+operations%22">Binary operations</searchLink><br /><searchLink fieldCode="DE" term="%22Binary+number+system%22">Binary number system</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Bitwise is a fundamental concept in computer science, involving specialized operations for handling logical calculations on binary numbers. One commonly used bitwise operation is AND, where if two binary bits are compared and both are 1, the result is 1. One of the problems is AND Queries, where we have to calculate by using the array A, in every query, how many results when an integer from array A & V has a result of K 1-bit in binary form. This problem has an array A with size N and Q queries. In this paper, we propose a novel solution for the AND Queries problem using Sum Over Subsets Dynamic Programming. Sum Over Subsets Dynamic Programming is a branch of Bitmask Dynamic Programming that utilizes subsets of numbers in a set to find the sum of subsets, aiding in solving the case study of AND Queries are a technique used to calculate the sum of values for all subsets of a given set or bitmask. By using this technique, the solution strategy begins with accepting inputs, identifying subproblems, and grouping subsets, modeling dynamic programming, and substitution using Sum Over Subsets, and Dynamic programming to derive the final result. Based on the experimental testing result, the solution using the Sum Over Subsets Dynamic Programming algorithm requires an average time of 1.121 seconds, which is nine times faster than the time needed, and a constant memory of 12 MB, which uses 0.05% of the required memory limit. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IAENG International Journal of Computer Science is the property of International Association of Engineers (IAENG) and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=192720771 |
| RecordInfo | BibRecord: BibEntity: Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 15 StartPage: 1343 Subjects: – SubjectFull: Dynamic programming Type: general – SubjectFull: Binary operations Type: general – SubjectFull: Binary number system Type: general – SubjectFull: Computational complexity Type: general – SubjectFull: Algorithms Type: general Titles: – TitleFull: Sum Over Subsets Dynamic Programming to Count K-Bits of AND Bitwise Operation Results. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Soelaiman, Rully – PersonEntity: Name: NameFull: Samsico, Alexander Weynard – PersonEntity: Name: NameFull: Purwananto, Yudhi IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 04 Text: Apr2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 1819656X Numbering: – Type: volume Value: 53 – Type: issue Value: 4 Titles: – TitleFull: IAENG International Journal of Computer Science Type: main |
| ResultId | 1 |
