Trung tâm cá nhân
Bài viết phát hành
từ bỏ
Bài viết phổ biến của tác giả
- Tìm số 0 đầu tiên trong một mảng bit
- Unix Hiển thị thông tin về các tập tin khớp với một trong hai mẫu
- Biểu thức chính quy thay thế nhiều tệp
- Ẩn lệnh từ xtrace
30
4
Tôi có một bitmap
uint64_t bitmap[10000]
Theo dõi các tài nguyên được phân bổ trong hệ thống. Bây giờ câu hỏi đặt ra là làm thế nào để tìm bit chưa đặt (bit không) đầu tiên trong bản đồ bitmap này một cách hiệu quả?
Tôi biết rằng glibc có ffsll(unsigned long long) để tìm bit thiết lập đầu tiên, tôi cho rằng nó được thực hiện bằng cách sử dụng lệnh phần cứng.
Để sử dụng hàm này trong ví dụ của tôi, trước tiên tôi cần khởi tạo mảng để đặt mọi bit thành 1, sau đó khi phân bổ tài nguyên, tôi phải tìm kiếm tuyến tính trong mảng để tìm từ đầu tiên không phải số 0. Sau đó sử dụng ffsll() để tìm bit set đầu tiên.
Tôi có thể làm nhanh hơn bằng cách nào?
Cập nhật: Tôi đang sử dụng CPU x86-64.
1 Câu trả lời
Bạn có thể duy trì bitmapCây, để tìm tập bit thấp nhất một cách hiệu quả. Trên CPU 64 bit, bạn chỉ cần đặt độ sâu của cây thành 3 để theo dõi 4096 phần tử 64 bit - điều này có nghĩa là chỉ có ba ffsll Gọi.
Về cơ bản, điều này được thực hiện bằng cách chia mảng thành các khối 64 từ và chỉ định chỉ mục 64 bit cho mỗi khối. Một bit của từ chỉ mục được thiết lập nếu và chỉ nếu từ tập bit tương ứng có tất cả các bit được thiết lập. Khi bạn thay đổi một bit trong một bitset, bạn sẽ điều chỉnh từ chỉ mục tương ứng.
Sau đó, bạn có thể xây dựng một mảng chỉ mục khác ở trên cùng để tạo thành một cây.
Phải mất thêm một chút công sức cho mỗi lần thay đổi bit, nhưng tổng lượng công sức (và dung lượng lưu trữ) phát sinh không đáng kể so với chi phí bạn tiết kiệm được khi không phải tìm kiếm tuyến tính trên bitset khi bạn cần một bit trống.
Liên quan đến c - tìm số không đầu tiên trong một mảng bit, chúng ta tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/14866848/
30
4
0
Câu hỏi này đã có câu trả lời tại đây: Các cách khác nhau để tải tệp dưới dạng InputStream (6 câu trả lời) Đã đóng 8 năm trước. Trong gradle java của tôi
Với một lớp Người dùng: class Người dùng cuối Tôi muốn định nghĩa một hằng số mới bằng cách sử dụng .class_eval. Vì vậy: User.class_eval { AVOCADO = 'fruit' } Nếu tôi thử
Điều này nghe có vẻ lạ nhưng tôi đang phát triển một plugin cần tìm các phần tử bên trong div hoặc chính div đó. Script tìm kiếm phần tử dựa trên lựa chọn của người dùng, nhưng nội dung (bao gồm cả đánh dấu) là khác nhau. Vì vậy, tập lệnh sẽ tìm kiếm phần tử như sau: $('.block').f
đóng cửa. Câu hỏi này cần có thông tin chi tiết hoặc rõ ràng. Hiện tại không chấp nhận câu trả lời. Bạn có muốn cải thiện câu hỏi này không? Thêm chi tiết và làm rõ câu hỏi bằng cách chỉnh sửa bài đăng này. Đã đóng 7 năm trước. Cải thiện th
Tôi cần tìm và xóa một giá trị trong nhiều cặp được sắp xếp theo hàm của riêng tôi. Rõ ràng là .find luôn trả về trình lặp đến cuối chứ không phải đến giá trị được tìm kiếm. Có mẹo nào không? Đây là hàm: struct cmp { bool operato
Trợ giúp! Tôi phải làm thế nào để tìm và xóa các dấu gạch dưới ở đầu bằng cách lặp qua việc xem các ký tự và đếm số dấu gạch dưới trước khi một ký tự hợp lệ xuất hiện. Cũng như lặp ngược lại từ cuối chuỗi để tìm bất kỳ dấu gạch dưới nào ở cuối. Tôi có thể sử dụng phương pháp bên dưới để xóa dấu gạch dưới, nhưng làm thế nào để lặp lại để tìm dấu gạch dưới?
Nếu bạn có xml sau trong $(xml), bạn đang lười biếng: $(xml).find("animal").find("dog").find("beagle").text() Có lớp nào trong jQuery không
Làm thế nào để tìm giao điểm của 4 tệp? Tôi đã sử dụng grep -Fx -f 1.txt 2.txt 3.txt 4.txt nhưng có vẻ như nó chỉ hoạt động với 2 tệp. Tương tự như vậy, comm -12 1.txt 2.txt không thể mở rộng thành 4
Tôi đã ước tính tư thế của điểm đánh dấu và thu được các giá trị rvec và tvec. Tôi không biết cách tìm tâm của nó vì tôi cần vẽ một hình trụ đòi hỏi giá trị tâm. Tôi có thể làm điều này bằng cách nào? Tvec của câu trả lời tốt nhất là bản dịch của điểm đánh dấu từ gốc (x,y
Tôi có một nhiệm vụ cần tìm giao điểm của 2 danh sách liên kết đơn (một-một). Tôi cũng phải làm điều này cho 2 danh sách liên kết đôi (kép so với đôi): Đối với các danh sách liên kết đơn, tôi đã sắp xếp cả hai danh sách bằng mergeSort() và sau đó so sánh từng mục
Tôi mới làm quen với R và tôi có một ma trận vuông có kích thước 100x100. Tôi muốn tìm giá trị riêng lớn nhất của ma trận này. Tôi đã thử is.indefinite(x) nhưng nó lại nói is.indefinite(x): đối số x là
Xin chào, tôi mới làm quen với svg và JavaScript và tôi đang cố gắng làm cho một số phần tử svg bật lên (bằng cách thay đổi tỷ lệ) khi chuột di chuyển qua phần tử svg và ngược lại khi chuột rời khỏi phần tử svg. Tôi đã có thể tạo ra svg
Tôi đang cố gắng viết một lớp cho một dự án scala nhưng tôi gặp lỗi này ở nhiều nơi khi sử dụng các từ khóa như class, def, while, v.v. Nó xảy ra ở những nơi như thế này: var continue = true while (conti
Tôi có hai khung dữ liệu pandas được lấy từ một cột và đặt cột ngày làm chỉ mục, do đó bây giờ tôi có hai Series. Tôi cần tìm mối tương quan của các chuỗi này. Sau đây là một vài dòng từ dfd: thay đổi chỉ mục 2018-
Tôi đang cố gắng điều chỉnh Vagrantfile của mình để nó tự động tạo một thư mục trong thư mục gốc của dự án nếu thư mục đó bị thiếu. Thư mục đã được tạo nhưng tôi không thể tìm thấy nơi để tạo thư mục đó. Tôi tìm thấy thông tin này có sẵn tại Vagrant::Environ
Tôi đang cố gắng tìm vị trí của Test3 trong jquery, ai đó vui lòng hướng dẫn tôi đi đúng hướng. Tôi cần jquery để hiển thị 5 Test7 Test2 Test6 Test5 Test3 Test8 Cảm ơn bạn
Chào buổi sáng mọi người, tôi có một danh sách hình ảnh như thế này: Khi sử dụng jQuery, làm sao tôi có thể tìm thấy tất cả các hình ảnh src trong ul#preload có chứa một chuỗi cụ thể (ví dụ: "green") giống như... var new_src = j
Tôi đang phát triển một ứng dụng có thể chỉnh sửa các tệp Excel. Làm thế nào để tìm ô được sử dụng cuối cùng trong bất kỳ hàng nào? Ví dụ: Ô được sử dụng cuối cùng trong hàng số => 5 Câu trả lời hay nhất Để tìm ô cuối cùng trong hàng, bạn cần Kết thúc phạm vi
Tôi mới bắt đầu sử dụng React Native và cần trợ giúp để điều hướng đến màn hình được bảo vệ khi tìm thấy mã thông báo. Tôi nên tìm mã thông báo ở đâu khi ứng dụng tải? Làm thế nào để điều hướng người dùng một lần mà không cần gọi điều hướng nhiều lần
Thật kỳ lạ... Trang này có được bảo vệ không hay tôi không biết? Tôi thử nhấp vào trang neo tiếp theo. Xem trang này trước. Tôi đã cố gắng lấy phần tử bằng cách sử dụng var buttonNext =
Tôi là một lập trình viên xuất sắc, rất giỏi!