Sum Over Subsets Dynamic Programming to Count K-Bits of AND Bitwise Operation Results.

Saved in:

Bibliographic Details
Title:	Sum Over Subsets Dynamic Programming to Count K-Bits of AND Bitwise Operation Results.
Authors:	Soelaiman, Rully¹ rully130270@gmail.com, Samsico, Alexander Weynard² samsicoweynard@gmail.com, Purwananto, Yudhi¹ 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

Description
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]
ISSN:	1819656X